11 Dec 2011
Given 2 sorted arrays, n and m in length, find the median.
First, let's just assume that the numbers are unique and
(n+m) is odd.
The first obvious solution that comes to me takes
We use 2 pointers starting on the beginning of each array. We walk them one at a time in increasing order. If we have walk
(n+m)/2 times, then the latest touched element is the median.
Anyway, on Leetcode.com, it states that the solution should take only
O(log(m+n)) requires some sort of binary search.
Anyway, let's make some random observations as I always do.
If we combine the two arrays and keep the order, the median is at the
Let's throw out some examples:
1 3 5 7 9 11 13 2 4 6 8 10 12 1 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 4 7 8 9 5 6 10 11 12 13
What we can do with
O(log n) is to pick one element in the first array and find the lesser elements in the second array.
Let's say we pick the element
x-th from the first array. We only need to consider the first
(((n+m)/2) - x) elements in the second array.
This observation is something. We pick the element
i-th in the first array, say
a[i], and we find all the lesser elements in the second array. Let's say
b[j] is the biggest element that is less than
(i+j) == (n+m)/2, then we got the answer.
(i+j) > (n+m)/2, then we try again with the
(i+j) < (n+m)/2, then we try again with the
(i + (n-i)/2)-thelement.
You know, the binary search algorithm. You need to refine the algorithm, a little.