1. Let A and B be 2 sorted arrays
2. We can check whether A[i] is median in constant time.
3. Suppose A[i] is median, then it is greater than exactly i-1 elements in A, and it has to be exaclty n/2 -(i-1) elements in B.
4. It requires constant time to check if B[j] < A[i] < B[j + 1]
5. If A[i] is not the median, then depending on whether A[i] is greater or less than B[j] and B[j + 1], you know that A[i] is either greater than or less than the median. Thus you can binary search for A[i] in (lg n)
1. Let A and B be 2 sorted arrays
2. We can check whether A[i] is median in constant time.
3. Suppose A[i] is median, then it is greater than exactly i-1 elements in A, and it has to be exaclty n/2 -(i-1) elements in B.
4. It requires constant time to check if B[j] < A[i] < B[j + 1]
5. If A[i] is not the median, then depending on whether A[i] is greater or less than B[j] and B[j + 1], you know that A[i] is either greater than or less than the median. Thus you can binary search for A[i] in (lg n)
See solution here :
http://ocw.mit.edu/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/30C68118-E436-4FE3-8C79-6BAFBB07D935/0/ps9sol.pdf