给定两个排序数组a[]和b[]，任务是在O（log（min（n，m））中查找这些排序数组的中值，其中n是第一个数组中的元素数，m是第二个数组中的元素数。 先决条件： 两个不同大小的排序数组的中值。
null
例如：
Input : ar1[] = {-5, 3, 6, 12, 15} ar2[] = {-12, -10, -6, -3, 4, 10} The merged array is : ar3[] = {-12, -10, -6, -5 , -3, 3, 4, 6, 10, 12, 15}Output : The median is 3.Input : ar1[] = {2, 3, 5, 8} ar2[] = {10, 12, 14, 16, 18, 20} The merged array is : ar3[] = {2, 3, 5, 8, 10, 12, 14, 16, 18, 20} if the number of the elements are even, so there are two middle elements, take the average between the two : (10 + 12) / 2 = 11. Output : The median is 11.
注： 在总数为偶数的情况下，如果我们想要返回合并数组中存在的中值，我们可以返回（n+m）/2或（n+m）/2–1位置的元素。在这种情况下，中位数可以是10或12。
推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。
方法： 开始将两个数组分成两组（不是两部分，但两个分区的元素数应该相同）。前半部分包含来自第一个和第二个数组的一些第一个元素，后半部分包含来自第一个和第二个数组的其余（或最后）元素。因为数组可以有不同的大小，所以这并不意味着要从每个数组中取出一半。下面的例子澄清了这个解释。达到这样一个条件：前半部分中的每个元素小于或等于后半部分中的每个元素。
如何达到这种状态？ 偶数的例子。假设找到了分区。因为A[]和B[]是两个排序数组，a1小于或等于a2，b2小于或等于b3。现在，检查a1是否小于或等于b3，b2是否小于或等于a2。如果是这种情况，这意味着前半部分中的每个元素都小于或等于后半部分中的每个元素，因为a1大于或等于A[]中它前面（a0）的每个元素，b2大于或等于B[]中它前面（b1和b0）的每个元素。如果总数为偶数，中值将是a1、b2最大值与a2、b3最小值之间的平均值，但如果总数为奇数，中值将是a2、b2最大值。但如果不是这两种情况，则有两种选择（参考偶数示例）： b2>a2或a1>b3 如果b2>a2，则在数组右侧搜索，如果a1>b3，则在数组左侧搜索，直到找到所需条件。
![图片[1]-以O（log（min（n，m））表示的两个大小不同的排序数组的中值-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/geeks_examples.png)
为什么上述情况会导致中位数？ 中位数是数组的（n+1）/2最小元素，这里，中位数是两个数组中的（n+m+1）/2最小元素。如果上半部分的所有元素小于（或等于）下半部分的所有元素，如果总数为奇数，只需计算上半部分最后两个元素之间的最大值（在我们的示例中为a2和b2），这将导致我们得到两个数组中（n+m+1）/2最小的元素，即中值（（7+4+1）/2=6）。但如果总数为偶数，则计算前半部分中最后两个元素的最大值（在本例中为a1和b2）与阵列中的连续数之间的平均值，即后半部分中前两个元素的最小值（在本例中为a2和b3）。
划分的过程： 要将其分成两半，请使分区数组A[]的索引+分区数组B[]的索引等于元素总数加1除以2，即（n+m+1）/2（+1，如果元素总数为奇数）。 首先，定义两个变量：min_index和max_index，并将min_index初始化为0，将max_index初始化为较小数组的长度。在下面的例子中，[]是较小的数组。 要划分A[]，使用公式（最小索引+最大索引）/2并将其插入变量i。要划分B[]，使用公式（n+m+1）/2–i并将其插入变量j。 变量i表示从A[]插入前半部分的元素数量，j表示从B[]插入前半部分的元素数量，其余元素将插入后半部分。 看看下面的例子：
注意：如果给定数组中有一个数组为空，则分区不工作：
例如： 如果arr1=[2]，则arr2=[]通过此 “（n+m+1）/2” 公式计算 i=0 和价值 j=1 这会给出索引外错误，因为arr2是空的，arr2[j]会给出索引外错误。您必须通过检查一个数组是否为空来处理这种情况，您只需返回另一个数组的介质即可。
例如： 如果arr1的长度为0：
arr2的返回中值
否则，如果arr2的长度为0：
arr1的返回中值
例1：
![图片[2]-以O（log（min（n，m））表示的两个大小不同的排序数组的中值-yiteyi-C++库](https://media.geeksforgeeks.org/wp-content/uploads/dia1.png)
![图片[3]-以O（log（min（n，m））表示的两个大小不同的排序数组的中值-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/geeks_dia2-1.png)
例2 （此示例指返回合并数组中存在的中值的条件） :
![图片[4]-以O（log（min（n，m））表示的两个大小不同的排序数组的中值-yiteyi-C++库](https://media.geeksforgeeks.org/wp-content/uploads/dia3.png)
![图片[5]-以O（log（min（n，m））表示的两个大小不同的排序数组的中值-yiteyi-C++库](https://media.geeksforgeeks.org/wp-content/uploads/dia4.png)
![图片[6]-以O（log（min（n，m））表示的两个大小不同的排序数组的中值-yiteyi-C++库](https://media.geeksforgeeks.org/wp-content/uploads/dia5.png)
以下是上述方法的实施情况：
C++
// CPP code for median with case of returning // double value when even number of elements are // present in both array combinely #include<bits/stdc++.h> using std::cout; int maximum( int a, int b); int minimum( int a, int b); // Function to find median of two sorted arrays double findMedianSortedArrays( int *a, int n, int *b, int m) { int min_index = 0, max_index = n, i, j, median; while (min_index <= max_index) { i = (min_index + max_index) / 2; j = ((n + m + 1) / 2) - i; // If j is negative then the partition is not // possible having i elements from array i if (j < 0) { max_index = i-1; continue ; } // if i = n, it means that Elements from a[] in // the second half is an empty set. and if j = 0, // it means that Elements from b[] in the first // half is an empty set. so it is necessary to // check that, because we compare elements from // these two groups. // Searching on right if (i < n && j > 0 && b[j - 1] > a[i]) min_index = i + 1; // if i = 0, it means that Elements from a[] in // the first half is an empty set and if j = m, // it means that Elements from b[] in the second // half is an empty set. so it is necessary to // check that, because we compare elements // from these two groups. // searching on left else if (i > 0 && j < m && b[j] < a[i - 1]) max_index = i - 1; // we have found the desired halves. else { // this condition happens when we don't have any // elements in the first half from a[] so we // returning the last element in b[] from // the first half. if (i == 0) median = b[j - 1]; // and this condition happens when we don't // have any elements in the first half from // b[] so we returning the last element in // a[] from the first half. else if (j == 0) median = a[i - 1]; else median = maximum(a[i - 1], b[j - 1]); break ; } } // calculating the median. // If number of elements is odd there is // one middle element. if ((n + m) % 2 == 1) return ( double )median; // Elements from a[] in the second half is an empty set. if (i == n) return (median+b[j]) / 2.0; // Elements from b[] in the second half is an empty set. if (j == m) return (median + a[i]) / 2.0; return (median + minimum(a[i], b[j])) / 2.0; } // Function to find max int maximum( int a, int b) { return a > b ? a : b; } // Function to find minimum int minimum( int a, int b) { return a < b ? a : b; } // Driver code int main() { int a[] = {900}; int b[] = { 10, 13, 14}; int n = sizeof (a) / sizeof ( int ); int m = sizeof (b) / sizeof ( int ); // we need to define the smaller array as the // first parameter to make sure that the // time complexity will be O(log(min(n,m))) if (n < m) cout << "The median is : " << findMedianSortedArrays(a, n, b, m); else cout << "The median is : " << findMedianSortedArrays(b, m, a, n); return 0; } |
JAVA
// Java code for median with // case of returning double // value when even number of // elements are present in // both array combinely import java.io.*; class GFG { static int []a = new int []{ 900 }; static int []b = new int []{ 10 , 13 , 14 }; // Function to find max static int maximum( int a, int b) { return a > b ? a : b; } // Function to find minimum static int minimum( int a, int b) { return a < b ? a : b; } // Function to find median // of two sorted arrays static double findMedianSortedArrays( int n, int m) { int min_index = 0 , max_index = n, i = 0 , j = 0 , median = 0 ; while (min_index <= max_index) { i = (min_index + max_index) / 2 ; j = ((n + m + 1 ) / 2 ) - i; // if i = n, it means that Elements // from a[] in the second half is an // empty set. and if j = 0, it means // that Elements from b[] in the first // half is an empty set. so it is // necessary to check that, because we // compare elements from these two // groups. Searching on right if (i < n && j > 0 && b[j - 1 ] > a[i]) min_index = i + 1 ; // if i = 0, it means that Elements // from a[] in the first half is an // empty set and if j = m, it means // that Elements from b[] in the second // half is an empty set. so it is // necessary to check that, because // we compare elements from these two // groups. searching on left else if (i > 0 && j < m && b[j] < a[i - 1 ]) max_index = i - 1 ; // we have found the desired halves. else { // this condition happens when we // don't have any elements in the // first half from a[] so we // returning the last element in // b[] from the first half. if (i == 0 ) median = b[j - 1 ]; // and this condition happens when // we don't have any elements in the // first half from b[] so we // returning the last element in // a[] from the first half. else if (j == 0 ) median = a[i - 1 ]; else median = maximum(a[i - 1 ], b[j - 1 ]); break ; } } // calculating the median. // If number of elements is odd // there is one middle element. if ((n + m) % 2 == 1 ) return ( double )median; // Elements from a[] in the // second half is an empty set. if (i == n) return (median + b[j]) / 2.0 ; // Elements from b[] in the // second half is an empty set. if (j == m) return (median + a[i]) / 2.0 ; return (median + minimum(a[i], b[j])) / 2.0 ; } // Driver code public static void main(String args[]) { int n = a.length; int m = b.length; // we need to define the // smaller array as the // first parameter to // make sure that the // time complexity will // be O(log(min(n,m))) if (n < m) System.out.print( "The median is : " + findMedianSortedArrays(n, m)); else System.out.print( "The median is : " + findMedianSortedArrays(m, n)); } } // This code is contributed by // Manish Shaw(manishshaw1) |
Python3
# Python code for median with # case of returning double # value when even number # of elements are present # in both array combinely median = 0 i = 0 j = 0 # def to find max def maximum(a, b): return a if a > b else b # def to find minimum def minimum(a, b): return a if a < b else b # def to find median # of two sorted arrays def findMedianSortedArrays(a, n, b, m): # if a is empty if n = = 0 : # if b has even no. of elements if m % 2 = = 0 : return (b[m / 2 ] + b[(m / 2 ) + 1 ]) / 2 # if b has odd no. of elements else : return b[ int (m / 2 )] # if b is empty elif m = = 0 : # if a has even no. of elements if n % 2 = = 0 : return (a[n / 2 ] + a[(n / 2 ) + 1 ]) / 2 # if a has odd no. of elements else : return a[ int (n / 2 )] global median, i, j min_index = 0 max_index = n while (min_index < = max_index): i = int ((min_index + max_index) / 2 ) j = int (((n + m + 1 ) / 2 ) - i) # if i = n, it means that # Elements from a[] in the # second half is an empty # set. and if j = 0, it # means that Elements from # b[] in the first half is # an empty set. so it is # necessary to check that, # because we compare elements # from these two groups. # Searching on right if (i < n and j > 0 and b[j - 1 ] > a[i]): min_index = i + 1 # if i = 0, it means that # Elements from a[] in the # first half is an empty # set and if j = m, it means # that Elements from b[] in # the second half is an empty # set. so it is necessary to # check that, because we compare # elements from these two groups. # searching on left elif (i > 0 and j < m and b[j] < a[i - 1 ]): max_index = i - 1 # we have found the # desired halves. else : # this condition happens when # we don't have any elements # in the first half from a[] # so we returning the last # element in b[] from the # first half. if (i = = 0 ): median = b[j - 1 ] # and this condition happens # when we don't have any # elements in the first half # from b[] so we returning the # last element in a[] from the # first half. elif (j = = 0 ): median = a[i - 1 ] else : median = maximum(a[i - 1 ], b[j - 1 ]) break # calculating the median. # If number of elements # is odd there is # one middle element. if ((n + m) % 2 = = 1 ): return median # Elements from a[] in the # second half is an empty set. if (i = = n): return ((median + b[j]) / 2.0 ) # Elements from b[] in the # second half is an empty set. if (j = = m): return ((median + a[i]) / 2.0 ) return ((median + minimum(a[i], b[j])) / 2.0 ) # Driver code a = [ 900 ] b = [ 10 , 13 , 14 ] n = len (a) m = len (b) # we need to define the # smaller array as the # first parameter to make # sure that the time complexity # will be O(log(min(n,m))) if (n < m): print ( "The median is : {}" . format (findMedianSortedArrays(a, n, b, m))) else : echo( "The median is : {}" . format (findMedianSortedArrays(b, m, a, n))) # This code is contributed # by Aditya Khare(adityaskhare123) |
C#
// C# code for median with case of returning // double value when even number of elements // are present in both array combinely using System; class GFG { // Function to find max static int maximum( int a, int b) { return a > b ? a : b; } // Function to find minimum static int minimum( int a, int b) { return a < b ? a : b; } // Function to find median of two sorted // arrays static double findMedianSortedArrays( ref int []a, int n, ref int []b, int m) { int min_index = 0, max_index = n, i = 0, j = 0, median = 0; while (min_index <= max_index) { i = (min_index + max_index) / 2; j = ((n + m + 1) / 2) - i; // if i = n, it means that Elements // from a[] in the second half is an // empty set. and if j = 0, it means // that Elements from b[] in the first // half is an empty set. so it is // necessary to check that, because we // compare elements from these two // groups. Searching on right if (i < n && j > 0 && b[j - 1] > a[i]) min_index = i + 1; // if i = 0, it means that Elements // from a[] in the first half is an // empty set and if j = m, it means // that Elements from b[] in the second // half is an empty set. so it is // necessary to check that, because // we compare elements from these two // groups. searching on left else if (i > 0 && j < m && b[j] < a[i - 1]) max_index = i - 1; // we have found the desired halves. else { // this condition happens when we // don't have any elements in the // first half from a[] so we // returning the last element in // b[] from the first half. if (i == 0) median = b[j - 1]; // and this condition happens when // we don't have any elements in the // first half from b[] so we // returning the last element in // a[] from the first half. else if (j == 0) median = a[i - 1]; else median = maximum(a[i - 1], b[j - 1]); break ; } } // calculating the median. // If number of elements is odd // there is one middle element. if ((n + m) % 2 == 1) return ( double )median; // Elements from a[] in the second // half is an empty set. if (i == n) return (median+b[j]) / 2.0; // Elements from b[] in the second // half is an empty set. if (j == m) return (median + a[i]) / 2.0; return (median + minimum(a[i], b[j])) / 2.0; } // Driver code static void Main() { int []a = new int []{900}; int []b = new int []{ 10, 13, 14}; int n = a.Length; int m = b.Length; // we need to define the smaller // array as the first parameter to // make sure that the time // complexity will be O(log(min(n,m))) if (n < m) Console.Write( "The median is : " + findMedianSortedArrays( ref a, n, ref b, m)); else Console.Write( "The median is : " + findMedianSortedArrays( ref b, m, ref a, n)); } } // This code is contributed by Manish Shaw // (manishshaw1) |
PHP
<?php // PHP code for median with // case of returning double // value when even number // of elements are present // in both array combinely $median = 0; $i = 0; $j = 0; // Function to find max function maximum( $a , $b ) { return $a > $b ? $a : $b ; } // Function to find minimum function minimum( $a , $b ) { return $a < $b ? $a : $b ; } // Function to find median // of two sorted arrays function findMedianSortedArrays(& $a , $n , & $b , $m ) { global $median , $i , $j ; $min_index = 0; $max_index = $n ; while ( $min_index <= $max_index ) { $i = intval (( $min_index + $max_index ) / 2); $j = intval ((( $n + $m + 1) / 2) - $i ); // if i = n, it means that // Elements from a[] in the // second half is an empty // set. and if j = 0, it // means that Elements from // b[] in the first half is // an empty set. so it is // necessary to check that, // because we compare elements // from these two groups. // Searching on right if ( $i < $n && $j > 0 && $b [ $j - 1] > $a [ $i ]) $min_index = $i + 1; // if i = 0, it means that // Elements from a[] in the // first half is an empty // set and if j = m, it means // that Elements from b[] in // the second half is an empty // set. so it is necessary to // check that, because we compare // elements from these two groups. // searching on left else if ( $i > 0 && $j < $m && $b [ $j ] < $a [ $i - 1]) $max_index = $i - 1; // we have found the // desired halves. else { // this condition happens when // we don't have any elements // in the first half from a[] // so we returning the last // element in b[] from the // first half. if ( $i == 0) $median = $b [ $j - 1]; // and this condition happens // when we don't have any // elements in the first half // from b[] so we returning the // last element in a[] from the // first half. else if ( $j == 0) $median = $a [ $i - 1]; else $median = maximum( $a [ $i - 1], $b [ $j - 1]); break ; } } // calculating the median. // If number of elements // is odd there is // one middle element. if (( $n + $m ) % 2 == 1) return $median ; // Elements from a[] in the // second half is an empty set. if ( $i == $n ) return (( $median + $b [ $j ]) / 2.0); // Elements from b[] in the // second half is an empty set. if ( $j == $m ) return (( $median + $a [ $i ]) / 2.0); return (( $median + minimum( $a [ $i ], $b [ $j ])) / 2.0); } // Driver code $a = array (900); $b = array (10, 13, 14); $n = count ( $a ); $m = count ( $b ); // we need to define the // smaller array as the // first parameter to make // sure that the time complexity // will be O(log(min(n,m))) if ( $n < $m ) echo ( "The median is : " . findMedianSortedArrays( $a , $n , $b , $m )); else echo ( "The median is : " . findMedianSortedArrays( $b , $m , $a , $n )); // This code is contributed // by Manish Shaw(manishshaw1) ?> |
Javascript
<script> // Javascript code for median with // case of returning double // value when even number of // elements are present in // both array combinely let a=[900]; let b=[10, 13, 14]; // Function to find max function maximum(a,b) { return a > b ? a : b; } // Function to find minimum function minimum(a,b) { return a < b ? a : b; } // Function to find median // of two sorted arrays function findMedianSortedArrays(n,m) { let min_index = 0, max_index = n, i = 0, j = 0, median = 0; while (min_index <= max_index) { i = Math.floor((min_index + max_index) / 2); j = Math.floor((n + m + 1) / 2) - i; // if i = n, it means that Elements // from a[] in the second half is an // empty set. and if j = 0, it means // that Elements from b[] in the first // half is an empty set. so it is // necessary to check that, because we // compare elements from these two // groups. Searching on right if (i < n && j > 0 && b[j - 1] > a[i]) min_index = i + 1; // if i = 0, it means that Elements // from a[] in the first half is an // empty set and if j = m, it means // that Elements from b[] in the second // half is an empty set. so it is // necessary to check that, because // we compare elements from these two // groups. searching on left else if (i > 0 && j < m && b[j] < a[i - 1]) max_index = i - 1; // we have found the desired halves. else { // this condition happens when we // don't have any elements in the // first half from a[] so we // returning the last element in // b[] from the first half. if (i == 0) median = b[j - 1]; // and this condition happens when // we don't have any elements in the // first half from b[] so we // returning the last element in // a[] from the first half. else if (j == 0) median = a[i - 1]; else median = maximum(a[i - 1], b[j - 1]); break ; } } // calculating the median. // If number of elements is odd // there is one middle element. if ((n + m) % 2 == 1) return median; // Elements from a[] in the // second half is an empty set. if (i == n) return (median + b[j]) / 2.0; // Elements from b[] in the // second half is an empty set. if (j == m) return (median + a[i]) / 2.0; return (median + minimum(a[i], b[j])) / 2.0; } // Driver code let n = a.length; let m = b.length; // we need to define the // smaller array as the // first parameter to // make sure that the // time complexity will // be O(log(min(n,m))) if (n < m) document.write( "The median is : " + findMedianSortedArrays(n, m)); else document.write( "The median is : " + findMedianSortedArrays(m, n)); // This code is contributed by unknown2108 </script> |
输出：
The median is : 13.5
另一种方法： 相同的程序，但返回合并数组中存在的中值（（n+m）/2–1位置）：
C++
// C++ code for finding median of the given two // sorted arrays that exists in the merged array ((n+m) / 2 - 1 position) #include<bits/stdc++.h> using std::cout; int maximum( int a, int b); // Function to find median of given two sorted arrays int findMedianSortedArrays( int *a, int n, int *b, int m) { int min_index = 0, max_index = n, i, j; while (min_index <= max_index) { i = (min_index + max_index) / 2; j = ((n + m + 1) / 2) - i; // if i = n, it means that Elements from a[] in // the second half is an empty set. If j = 0, it // means that Elements from b[] in the first half // is an empty set. so it is necessary to check that, // because we compare elements from these two groups. // searching on right if (i < n && j > 0 && b[j - 1] > a[i]) min_index = i + 1; // if i = 0, it means that Elements from a[] in the // first half is an empty set and if j = m, it means // that Elements from b[] in the second half is an // empty set. so it is necessary to check that, // because we compare elements from these two groups. // searching on left else if (i > 0 && j < m && b[j] < a[i - 1]) max_index = i - 1; // we have found the desired halves. else { // this condition happens when we don't have // any elements in the first half from a[] so // we returning the last element in b[] from // the first half. if (i == 0) return b[j - 1]; // and this condition happens when we don't have any // elements in the first half from b[] so we // returning the last element in a[] from the first half. if (j == 0) return a[i - 1]; else return maximum(a[i - 1], b[j - 1]); } } cout << "ERROR!!! " << "returning" ; return 0; } // Function to find maximum int maximum( int a, int b) { return a > b ? a : b; } // Driver code int main() { int a[] = {900}; int b[] = { 10,13,14}; int n = sizeof (a) / sizeof ( int ); int m = sizeof (b) / sizeof ( int ); // we need to define the smaller array as the first // parameter to make sure that the time complexity // will be O(log(min(n,m))) if (n < m) cout << "The median is: " << findMedianSortedArrays(a, n, b, m); else cout << "The median is: " << findMedianSortedArrays(b, m, a, n); return 0; } |
JAVA
// Java code for finding median of the // given two sorted arrays that exists // in the merged array ((n+m) / 2 - // 1 position) import java.io.*; class GFG{ // Function to find maximum static int maximum( int a, int b) { return a > b ? a : b; } // Function to find median // of given two sorted arrays static int findMedianSortedArrays( int []a, int n, int []b, int m) { int min_index = 0 , max_index = n, i, j; while (min_index <= max_index) { i = (min_index + max_index) / 2 ; j = ((n + m + 1 ) / 2 ) - i; // If i = n, it means that // Elements from a[] in the // second half is an empty // set. If j = 0, it means // that Elements from b[] // in the first half is an // empty set. so it is // necessary to check that, // because we compare elements // from these two groups. // searching on right if (i < n && j > 0 && b[j - 1 ] > a[i]) min_index = i + 1 ; // If i = 0, it means that // Elements from a[] in the // first half is an empty set // and if j = m, it means that // Elements from b[] in the // second half is an empty set. // so it is necessary to check // that, because we compare // elements from these two // groups. searching on left else if (i > 0 && j < m && b[j] < a[i - 1 ]) max_index = i - 1 ; // We have found the // desired halves. else { // This condition happens // when we don't have any // elements in the first // half from a[] so we // returning the last // element in b[] from // the first half. if (i == 0 ) return b[j - 1 ]; // And this condition happens // when we don't have any // elements in the first half // from b[] so we returning the // last element in a[] from the // first half. if (j == 0 ) return a[i - 1 ]; else return maximum(a[i - 1 ], b[j - 1 ]); } } System.out.print( "ERROR!!! " + "returning" ); return 0 ; } // Driver code public static void main(String[] args) { int []a = { 900 }; int []b = { 10 , 13 , 14 }; int n = a.length; int m = b.length; // We need to define the smaller // array as the first parameter // to make sure that the time // complexity will be O(log(min(n,m))) if (n < m) System.out.print( "The median is: " + findMedianSortedArrays(a, n, b, m)); else System.out.print( "The median is: " + findMedianSortedArrays(b, m, a, n)); } } // This code is contributed by rag2127 |
Python3
# Python 3 code for finding median # of the given two sorted arrays that # exists in the merged array # ((n+m) / 2 - 1 position) # Function to find median of given # two sorted arrays def findMedianSortedArrays(a, n, b, m): min_index = 0 max_index = n while (min_index < = max_index): i = (min_index + max_index) / / 2 j = ((n + m + 1 ) / / 2 ) - i # if i = n, it means that Elements # from a[] in the second half is # an empty set. If j = 0, it means # that Elements from b[] in the first # half is an empty set. so it is necessary # to check that, because we compare elements # from these two groups. searching on right if (i < n and j > 0 and b[j - 1 ] > a[i]): min_index = i + 1 # if i = 0, it means that Elements from # a[] in the first half is an empty set # and if j = m, it means that Elements # from b[] in the second half is an # a[] in the first half is an empty set # that, because we compare elements from # these two groups. searching on left elif (i > 0 and j < m and b[j] < a[i - 1 ]): max_index = i - 1 # we have found the desired halves. else : # this condition happens when we don't have # any elements in the first half from a[] so # we returning the last element in b[] from # the first half. if (i = = 0 ): return b[j - 1 ] # and this condition happens when we don't # have any elements in the first half from # b[] so we returning the last element in # a[] from the first half. if (j = = 0 ): return a[i - 1 ] else : return maximum(a[i - 1 ], b[j - 1 ]) print ( "ERROR!!! " , "returning" ) return 0 # Function to find maximum def maximum(a, b) : return a if a > b else b # Driver code if __name__ = = "__main__" : a = [ 900 ] b = [ 10 , 13 , 14 ] n = len (a) m = len (b) # we need to define the smaller array # as the first parameter to make sure # that the time complexity will be # O(log(min(n,m))) if (n < m): print ( "The median is: " , findMedianSortedArrays(a, n, b, m)) else : print ( "The median is: " , findMedianSortedArrays(b, m, a, n)) # This code is contributed # by ChitraNayal |
C#
// C# code for finding median // of the given two sorted // arrays that exists in the // merged array ((n+m) / 2 - // 1 position) using System; class GFG { // Function to find maximum static int maximum( int a, int b) { return a > b ? a : b; } // Function to find median // of given two sorted arrays static int findMedianSortedArrays( ref int []a, int n, ref int []b, int m) { int min_index = 0, max_index = n, i, j; while (min_index <= max_index) { i = (min_index + max_index) / 2; j = ((n + m + 1) / 2) - i; // if i = n, it means that // Elements from a[] in the // second half is an empty // set. If j = 0, it means // that Elements from b[] // in the first half is an // empty set. so it is // necessary to check that, // because we compare elements // from these two groups. // searching on right if (i < n && j > 0 && b[j - 1] > a[i]) min_index = i + 1; // if i = 0, it means that // Elements from a[] in the // first half is an empty set // and if j = m, it means that // Elements from b[] in the // second half is an empty set. // so it is necessary to check // that, because we compare // elements from these two // groups. searching on left else if (i > 0 && j < m && b[j] < a[i - 1]) max_index = i - 1; // we have found the // desired halves. else { // this condition happens // when we don't have any // elements in the first // half from a[] so we // returning the last // element in b[] from // the first half. if (i == 0) return b[j - 1]; // and this condition happens // when we don't have any // elements in the first half // from b[] so we returning the // last element in a[] from the // first half. if (j == 0) return a[i - 1]; else return maximum(a[i - 1], b[j - 1]); } } Console.Write ( "ERROR!!! " + "returning" ); return 0; } // Driver code static void Main() { int []a = new int []{900}; int []b = new int []{10, 13, 14}; int n = a.Length; int m = b.Length; // we need to define the smaller // array as the first parameter // to make sure that the time // complexity will be O(log(min(n,m))) if (n < m) Console.Write ( "The median is: " + findMedianSortedArrays( ref a, n, ref b, m)); else Console.Write ( "The median is: " + findMedianSortedArrays( ref b, m, ref a, n)); } } // This code is contributed by // Manish Shaw(manishshaw1) |
输出：
The median is: 13
时间复杂性： O（log（min（n，m）），其中n和m是给定排序数组的大小
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
