Median of Two Sorted Arrays

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

C++:
01 double kSmall(int A[],int m,int B[],int n,int k)
02 {
03       if(m==0) return B[k1];
04       if(n==0) return A[k1];
05       int a_hi;
06       int b_hi;
07       int a_lo=0;
08       if(k==1)  return A[0]<B[0]?A[0]:B[0];
09       if(m>k1){
10           a_hi=k2;
11           b_hi=0;
12       }else{
13           a_hi=m1;
14           b_hi=k1m;
15       }
16       while(a_lo<=a_hi){
17           int a_mid=(a_hi+a_lo)/2;
18           int d=a_hia_mid;
19           if(d>nb_hi1)
20               d=nb_hi1;
21           int b_mid=b_hi+d;
22           a_mid=a_hid;
23           if(A[a_mid]<B[b_mid]){
24               if((a_mid==m1)||(B[b_mid]<=A[a_mid+1]))
25                   return B[b_mid];
26               a_lo=a_mid+1;
27           }else{
28               if((b_mid==n1)||(A[a_mid]<=B[b_mid+1]))
29                   return A[a_mid];
30               a_hi=a_mid1;
31               b_hi=b_mid+1;
32           }
33       }
34       if(a_hi<0)
35           return B[k1];
36       if(B[0]>A[a_hi])
37           return A[a_hi+1];
38  }
39 
40 class Solution {
41 public:
42     double findMedianSortedArrays(int A[], int m, int B[], int n) {
43         // Start typing your C/C++ solution below
44         // DO NOT write int main() function
45         int k=m+n;
46         if(k%2==1)
47         {
48             return kSmall(A, m, B, n, (k+1)/2);
49         }
50         else
51         {
52             double result=kSmall(A,m,B,n,k/2)
53                     +kSmall(A,m,B,n,k/2+1);
54             return result/2;
55         }
56     }
57 };
Advertisements
This entry was posted in Array and linked list, Binary search. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s