Find the k-th smallest element in the union of two sorted arrays

Given two sorted arrays A, B of size m and n respectively. Find the k-th smallest element in the union of A and B. You can assume that there are no duplicate elements.

C++:
01 int 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 
09     if(k==1)
10         return A[0]<B[0]?A[0]:B[0];
11     if(m>k1){
12         a_hi=k2;
13         b_hi=0;
14     }else{
15         a_hi=m1;
16         b_hi=k1m;
17     }
18     while(a_lo<=a_hi){
19         int a_mid=(a_hi+a_lo)/2;
20         int d=a_hia_mid;
21         if(d>nb_hi1)
22             d=nb_hi1;
23         int b_mid=b_hi+d;
24         a_mid=a_hid;
25         if(A[a_mid]<B[b_mid]){
26             if((a_mid==m1)||(B[b_mid]<A[a_mid+1])){
27                 cout<<“case 1”<<endl;
28                 return B[b_mid];
29             }
30             a_lo=a_mid+1;
31         }else{
32             if((b_mid==n1)||(A[a_mid]<B[b_mid+1])){
33                 cout<<“case 2”<<endl;
34                 return A[a_mid];
35             }
36             a_hi=a_mid1;
37             b_hi=b_mid+1;
38         }
39     }
40     if(a_hi<0){
41         cout<<“case 3”<<endl;//A does not contain any first k element
42         return B[k1];
43     }
44     if(B[0]>A[a_hi]){
45         cout<<“case 4”<<endl;//B does not contain any first k element
46         return A[a_hi+1];
47     }
48 }
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