Daily Archives: December 26, 2014

Problem
The idea of the solution is very easy: use binary search. But when I wrote it, it took me a long time to verify the code.
For example, find the 4th number from a=[2, 4, 6, 8] and b=[5,9]
The result should be 6.

Solution

Basic idea:
a=[0,…,a_start, …, a_mid,…,a_end,…,a.length-1]
b=[0,…,b_start, …, b_mid,…,b_end,…,b.length-1]
Let half_length be number of element in a[a_start,…,a_mid] and b[b_start,…,b_mid].
find the kth from a and b.
Assume a[a_mid] is larger than b[b_mid].
If k < half_length, then we know that kth number can’t be in higher part of a, a[a_mid,…,a_end]. So next, we search a[a_start,…,a_mid-1] and b[b_start,…,b_end]
If k>=half_length, then we know that kth number can’t be in lower part of b, b[b_start,…,b_mid]. So next, we search a[a_start, a_end] and b[b_mid+1,…,b_end]. Meanwhile, we should set new value to k. k=k-(b_mid-b_start+1)

Return result when:
if(a_start>a_end){
return b[b_start+k-1];
}
if(b_start>b_end){
return a[a_start+k-1];
}

Case analysis1

a[a_mid]
half_length = 3
k>=half_length, so cut off lower part of a[], and k should deduct 2, which is 1, 3

1

b[] is out of bound, return a[a_s+k-1], which is 5

Case analysis2

a[a_mid]>b[b_mid]
half_length = 5
k>=half_length, so cut off lower part of b[], and k should deduct 3, which is 2, 4

a[a_mid]half_length = 4
k

b[] is out of bound, return a[a_s+k-1]=a[0+3-1], which is 5

My code is below:

1. public class MedianIn2SortedArray {
3.     public static void main(String[] args) {
4.         int[] a = {1,3,5,9,10};
5.         int[] b = {2,4,6,8};
6.         int median = findMedian(a,b);
7.         System.out.println(median);
8.     }
10.     public static int findMedian(int[] a, int[] b){
11.         int k = (a.length + b.length)/2;
12.         return findK(a, b, k, 0, a.length-1, 0, b.length-1);
14.     }
16.     public static int findK(int[] a, int[] b, int k, int a_start, int a_end, int b_start, int b_end){
17.         if(a_start>a_end){
18.             return b[b_start+k-1];
19.         }
20.         if(b_start>b_end){
21.             return a[a_start+k-1];
22.         }
23.         int a_mid = a_start+(a_end-a_start)/2;
24.         int b_mid = b_start+(b_end-b_start)/2;
25.         int half_len = a_mid-a_start+b_mid-b_start+2;
26.         if(a[a_mid]>b[b_mid]){
27.             if(k
28.                 //cut off the high part of large array, which is high of a[]
29.                 return findK(a, b, k, a_start, a_mid-1, b_start, b_end);
30.             }
31.             else{
32.                 //cut off the low part of small array, which is low of b[]
33.                 return findK(a, b, k-(b_mid-b_start+1),a_start, a_end, b_mid+1, b_end);
34.             }
35.         }
36.         else{
37.             if(k
38.                 //cut off the high part of large array, which is high of b[]
39.                 return findK(a, b, k, a_start, a_end, b_start, b_mid-1);
40.             }
41.             else{
42.                 //cut off the low part of small array, which is low of a[]
43.                 return findK(a, b, k-(a_mid-a_start+1), a_mid+1, a_end, b_start, b_end);
44.             }
45.         }
46.     }
47. }