Java Program to Solve Median of Two Sorted Array Problem
Median of two sorted arrays is a common problem which is asked in companies like Amazon, Google, Microsoft & Goldman Sachs. You can find the question in InterviewBit or LeetCode.
We have two sorted arrays A and B of size m and n respectively. We need to find the median of these two sorted arrays ( median of the array formed by merging both arrays ). The run time complexity should be O(log (m+n)).
A : [1 4 6] B : [2 5]
Output: 3.5 ( (3 + 4) / 2.0 = 3.5 )
A : [1 3 5] B : [2 4 6]
We can actually merge the two arrays & find out the median. But it will take O(m+n) time complexity.
We know the size of the median partition. In above cases it is 3. Median of 5 elements is 3 & median of 6 elements is avg of 3rd & 4th elements.
But left side elements in the partition can be part of both the arrays.
So we need to find indexes in both arrays where combined left side elements count is same as median partition. And elements in left hand side of each partition is less than the right side partitions of both arrays.
We can use binary search on the smaller size array to find the partition index. So time complexity will be O(log(min(m, n))).
You can find the working Java program for this problem below.