Median of Two Sorted Arrays

Problem

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)).

---

Idea1

• If m+n is old (奇数), the median is the number located in position (m+n)/2 of the array (A+B)
• If m+n is even (偶数), the median is the average of element in (m+n)/2 -1 and element in (m+n)/2
• So you need to judge if the m+n is old or even. Then, The problem is find the kth biggest element in array(A+B).
• After you decide the old and even of m+n, the idea of solution is to find the kth element in the array (A+B).

---

Idea2

• The idea is like Merge operation in CLRS. Retrieve the minimal element in A[] and B[] until you reach the median (Maybe two numbers for even case). Complexity is O(m+n)
• We need to carefully treat the cases when A[] is empty or B[] is empty at the beginning
• Use two parameter "front" , "rear" to record two elements for even case. And "rear" for old case.
• During the procedure to find the minimal element in A[]+B[]. You may meet the following cases
• Either A[] or B[] become empty, we just use the other sequence
• If A[] and B[] are non-empty, we will choose the smaller one.

---

Solution

This solution is for Idea2: