In the previous post, we discussed how to find median of two sorted array in same size. Now suppose two sorted array A and B which has length m and n respectively, the previous algorithm won't work as I explained before - the target median is no longer median in the newly generated array after each iteration.
However, the target median now becomes the n/2 smallest element of two sorted array. Astute reader may think: Can we can solve this issue - find the n/2 smallest element? The answer is yes. Instead of finding the median, we'd better see the problem this way.
Suppose the problem is to find Kth smallest element in the union of two sorted array. The median can be regarded as (m+n)/2 th smallest element in two sorted array.
Median of Two Sorted Array
In the previous post, we discussed how to find median of two sorted array in same size. Now suppose two sorted array A and B which has length m and n respectively, the previous algorithm won't work as I explained before - the target median is no longer median in the newly generated array after each iteration.
However, the target median now becomes the n/2 smallest element of two sorted array. Astute reader may think: Can we can solve this issue - find the n/2 smallest element? The answer is yes. Instead of finding the median, we'd better see the problem this way.
Suppose the problem is to find Kth smallest element in the union of two sorted array. The median can be regarded as (m+n)/2 th smallest element in two sorted array.