Median of Two sorted arrays -- Leetcode (O(logn) solution)

method 1: find Kth largest element of a[m] and b[n] sorted arrays.

double findKth(int a[], int m, int b[], int n, int k)
{
    //always assume that m is equal or smaller than n
    if (m > n)
        return findKth(b, n, a, m, k);
    if (m == 0)
        return b[k - 1];
    if (k == 1)                                 //end case
        return min(a[0], b[0]);

    //divide k into two parts: pa + pb.
    int pa = min(k / 2, m), pb = k - pa;
    if (a[pa - 1] < b[pb - 1])
        return findKth(a + pa, m - pa, b, n, k - pa);
    else if (a[pa - 1] > b[pb - 1])
        return findKth(a, m, b + pb, n - pb, k - pb);
    else
        return a[pa - 1];
}

class Solution
{
public:
    double findMedianSortedArrays(int A[], int m, int B[], int n)
    {
        int total = m + n;
        if (total & 0x1)
            return findKth(A, m, B, n, total / 2 + 1);
        else
            return (findKth(A, m, B, n, total / 2)
                    + findKth(A, m, B, n, total / 2 + 1)) / 2;
    }
};
我们可以看出，代码非常简洁，而且效率也很高。在最好情况下，每次都有k一半的元素被删除，所以算法复杂度为logk，由于求中位数时k为（m+n）/2，所以算法复杂度为log(m+n)。

/******************************************************************************/

method 2:
Algorithm：

1) Calculate the medians m1 and m2 of the input arrays ar1[]
   and ar2[] respectively.
2) If m1 and m2 both are equal then we are done.    //end case1.
     return m1 (or m2)
3) 1. If m1 is greater than m2, then median is present in one of the below two subarrays.
      a)  ar1[0....|_n/2_|]
      b)  ar2[|_n/2_|....n-1]
   2. If m2 is greater than m1, then median is present in one of the below two subarrays.
      a)  ar1[|_n/2_|....n-1]
      b)  ar2[0....|_n/2_|]
4) Repeat the above process until size of both the subarrays becomes 2.
5) If size of the two arrays is 2, use below formula to get the median.    //end case2.

       Median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2 ///!!Correct, ignore the head and tail, avoid merge step, so tricky!
Example:
      ar1[] = {1, 12, 15, 26, 38},
      ar2[] = {2, 13, 17, 30, 45}
For the two arrays: m1 = 15 and m2 = 17.
For the above ar1[] and ar2[], m1 < m2. So median lies in one of the following two subarrays:
              [15, 26, 38]
         [2,  13, 17]
Get:
      m1 = 26, m2 = 13. => m1 > m2. So the subarrays become:
               [15, 26]
      [13, 17]
Now size is 2, so median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2
                         = (max(15, 13) + min(26, 17))/2
                         = (15 + 17)/2
                         = 16
_______________________________________________________________________________
code:
#include <stdio.h>

#define Max(a,b) (a>b?a:b)
#define Min(a,b) (a<b?a:b)

int median(int ar[],int n){
if(n%2){
return ar[n/2];
}
else{
return (ar[n/2-1]+ar[n/2])/2;
}
}

int getMedian(int ar1[],int ar2[], int n){
if(n<=0){
printf("Error, illegal array length!\n");
return -1;
}
if(n==1){
return (ar1[0]+ar2[0])/2;
}
if(n==2){
return Max(ar1[0],ar2[0])+Min(ar1[1]+ar2[1])/2;       //end case 1, subarray size=2.
}
    m1= median(ar1,n);
    m2= median(ar2,n);

if(m1==m2) return m1;                                     //end case 2, m1==m2.
if(m1<m2){
   if(n%2){    //n is odd.
           return getMedian(ar1 + n/2, ar2, n - n/2);
}
  else{      // n is even.
  return getMedian(ar1 + n/2, ar2, n - n/2);
}
}
else{
if(n%2){
return getMedian(ar1, ar2 + n/2, n - n/2);
}
else{
return getMedian(ar1, ar2 + n/2, n - n/2);
}
}
}

int main()
{
    int ar1[] = {1, 12, 15, 26, 38};
    int ar2[] = {2, 13, 17, 30, 45};
    int n1 = sizeof(ar1)/sizeof(ar1[0]);
    int n2 = sizeof(ar2)/sizeof(ar2[0]);
    if (n1 == n2)
      printf("Median is %d", getMedian(ar1, ar2, n1));
    else
      printf("Unequal array size!");
    getchar();
    return 0;
}

/*
original merging method: O(n).
Suppose the sorted array is in ascending order.
median=(res[n-1]+res[n])/2.

method 1:
int get median(int a[],int b[],n){
    int res[2*n];
int i=n-1,j=n-1,k=2*n-1;

while(i>=0 && j>=0){
   if(a[i]<b[j]){
   res[k--]=b[j--];
   }
   else{
   res[k--]=a[i--];
}
}
if(i<0){
while(j>=0){
  res[k--]=b[j--];
}
}
else{
while(i>=0){
   res[k--]=a[i--];
}
}
return (res[n-1]+res[n])/2;
}

method 2: exist boundry case bugs!!
int get median(int a[],int b[],n){
    int res[2*n];
int i=0,j=0,ka=-1,kb=-1;

while(i<n&&j<n){
   if(a[i]<b[j]){
   ka=i;
i++;
if(ka+kb==n-2){
       m1=a[ka];
   }
   if(ka+kb==n-1){
       m2=a[ka];
   }
   }
   else{
   kb=j;
j++;
if(ka+kb==n-2){
       m1=b[kb];
   }
   if(ka+kb==n-1){
       m2=b[kb];
   }
}

 
}
if(i==n){
while(j<n){
  kb=j;
  j++;
  if(ka+kb==n-1){
       m2=b[kb];
  }
}
}
else{
while(i<n){
  ka=i;
  i++;
  if(ka+kb==n-1){
       m2=a[ka];
  }
}
}
return (m1+m2)/2;
}
*/