Previous post: Binary search done right: introduction

This is a LeetCode problem #4 (”hard”)

<aside> 💡 In this problem, you are given two sorted arrays of lengths n and m, and you need to find the median of their union as fast as possible. Recall that if an array has odd length [1,2,3], then the median is the element 3 situated in the middle, while for arrays of even lengths [1,2,3,4], the median is a half-sum of the two middle elements (2+3)/2=2.5 .

The required algorithm has a complexity O(log(n+m))

</aside>

Exercise. Can you prove that $\mathcal O(\log (n+m))$ is the lower bound for complexity?

• Solution to the exercise (click to expand).

There are two parts in this problem: first, come up with a solution, and the second, code it without messing around with +/- 1 . The second part may turn out to be surprisingly tricky, but with proper approach it can be handled without too much difficulties.

Idea of the solution using binary search

In the example above, the total size of the union is $8+11=19$, and so the half length is 19//2=9 . Their union is an array displayed below with the median marked.

[1, 1, 2, 3, 4, 5, 5, 6, 6, 7, 8, 11, 12, 15, 17, 18, 19, 20, 21]
                            ^

In fact, this selection of the first 9 elements corresponds to a union of the prefixes of these two arrays, respectively of lengths 3 and 6.

Note that the union of two prefixes does not necessarily correspond to a prefix of the union. On the contrary, any prefix of the union is indeed a union of two prefixes.

• Proof (click to expand).

Convention. There are two cases for the total length, the odd one and the even one. Instead of coding a separate algorithm for these two cases, let us assume that the prefix we are searching for has a length (n+m)//2. In both cases, we will need to find the next element to the prefix, and only then, depending on whether the total length is even or odd, either return this next element, or return the half-sum of this element with the last element of the prefix.

Since the length of the median is fixed, we need to find the length of the second prefix only. The length of the first prefix is calculated as the half-length minus the length of the second prefix.