I have been trying to understand why the following algorithm works to no avail.
1) Calculate the medians m1 and m2 of the input arrays ar1[]
and ar2[] respectively.
2) If m1 and m2 both are equal then we are done.
return m1 (or m2)
3) If m1 is greater than m2, then median is present in one
of the below two subarrays.
a) From first element of ar1 to m1 (ar1[0...|_n/2_|])
b) From m2 to last element of ar2 (ar2[|_n/2_|...n-1])
4) If m2 is greater than m1, then median is present in one
of the below two subarrays.
a) From m1 to last element of ar1 (ar1[|_n/2_|...n-1])
b) From first element of ar2 to m2 (ar2[0...|_n/2_|])
5) Repeat the above process until size of both the subarrays
becomes 2.
6) If size of the two arrays is 2 then use below formula to get
the median.
Median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2
My diffculty is in the steps 3 and 4 which are the core of the algorithm. Here is my thinking:
If m1 > m2 then m1 is greater than half of the elements in the merged array, so why would we want to explore ar1[0...|n/2|]?
Take a look at the following example. It demonstrates the case you're asking about.
ar1[] = {6, 7, 8, 9, 10}
ar2[] = {1, 2, 3, 4, 5}
If m1 > m2 then m1 is greater than half of the elements in the merged array, so why would we want to explore ar1[0...|n/2|]?
The key to understanding this algorithm is to look at what you're eliminating at each step, not just what you're keeping. It's true that since m1 > m2, we know that m1 is greater than half the elements in the merged array. It doesn't tell us where in relation to the merged median m1 is though. All we really know about the relation between ar1 and the merged median is that we can eliminate everything greater than m1 (and less than m2 from ar2). The median of the merged list is somewhere in what remains.
ar1[] = {6, 7, 8}
ar2[] = {3, 4, 5}