Daily bit(e) of C++ | Median of two sorted arrays
Daily bit(e) of C++ #126, Common interview problem: Median of two sorted arrays.
Today we will look at a common interview problem: Median of two sorted arrays.
Given two sorted arrays, return the median of the merged array in O(log(N)), where N is the total number of elements in the two arrays. If the total number of elements is even, return the average of the two middle elements.
For example, for input {1,3,5,7} and {1,1,2,4,8}, the result is 3.
Before continuing to read the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/P54dKTeaa.
Solution
Because of the sorted inputs, this problem calls for a binary search. However, we must avoid merging the two arrays to stay in log(n) territory.
We can do a parallel binary search, similar to searching in 2D space. If we divide both arrays into two parts, we can, in each iteration, remove the quadrant which cannot contain the median.
Finally, we can wrap this logic and return either the median or the average of the two middle elements if the total length is even.
