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(k>(m+n))
04          return 1;
05      int a_hi;
06      int b_hi;
07      int a_lo=0;
08      if(k==1)
09          return A[0]<B[0]?A[0]:B[0];
10      if(m>k1){
11          a_hi=k2;
12          b_hi=0;
13      }else{
14          a_hi=m1;
15          b_hi=k1m;
16      }
17      while(a_lo<=a_hi){
18          int a_mid=(a_hi+a_lo)/2;
19          int d=a_hia_mid;
20          if(d>nb_hi1)
21              d=nb_hi1;
22          int b_mid=b_hi+d;
23          a_mid=a_hid;
24          if(A[a_mid]<B[b_mid]){
25              if((a_mid==m1)||(B[b_mid]<=A[a_mid+1]))
26                  return B[b_mid];
27              a_lo=a_mid+1;
28          }else{
29              if((b_mid==n1)||(A[a_mid]<=B[b_mid+1]))
30                  return A[a_mid];
31              a_hi=a_mid1;
32              b_hi=b_mid+1;
33          }
34      }
35      if(a_hi<0)
36          return B[k1];
37      if(B[0]>A[a_hi])
38          return A[a_hi+1];
39 }
40 
41 double findMedian(int A[],int m){
42     if(m%2)
43         return A[m/2];
44     else
45         return (double)(A[m/21]+A[m/2])/2;
46 }
47 
48 double findMedianSortedArrays(int A[], int m, int B[], int n)
49 {
50         double result;
51         if(m==0){
52             result=findMedian(B,n);
53             return result;
54         }
55         if(n==0){
56             result=findMedian(A,m);
57             return result;
58         }
59         int s=m+n;
60         if(s%2){
61              int k=s/2;
62              result=kSmall(A,m,B,n,k+1);
63              return result;
64         }else{
65              int k=s/2;
66              double p=kSmall(A,m,B,n,k);
67              double q=kSmall(A,m,B,n,k+1);
68              result=(p+q)/2.0;
69              return result;
70         }
71 }
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