O(log(m + n)) and O(m + n) Solutions of Median of Two Sorted Arrays
This is a LeetCode problem:
It is not hard to come out a solution with O(m + n) or O(log(m + n)), but it’s really tricky to deal with boundary conditions.
A O(log(m + n)) solution should use something like binary search. I referenced an answer in the discussion board, and wrote my O(log(m + n)) solution. The idea is to make the median index as the k of the k-lowest search problem. For even length, the two median indices are (m + n + 1) >> 1 and (m + n + 2) >> 1; for odd length, (m + n + 1) >> 1 and (m + n + 2) >> 1 yield the same results! That’s really clever. With the median index, we find the k-lowest value in a recursion function. Here is the code:
For the brute force solution, with O(m + n) complexity, we keep sorting the two arrays by comparing the current values until we reach the median index: