Binary Search
Searching for a split
The hardest binary search in the set. The thing being searched for is not a value but a place to cut.
The problem, and the answer to give first
Two sorted arrays, and you need the median of their combined contents in logarithmic time.
Merging them takes O(n + m) and is trivially correct. Say that first. The logarithmic solution exists and is genuinely fiddly, and offering the linear one as a baseline before attempting it is the right order.
Key idea
What the median really asks for
Forget medians for a moment. Imagine cutting each array into a left part and a right part, so that the two left parts together hold exactly half of all the elements.
If every element in the combined left part is at or below every element in the combined right part, then that cut has separated the smaller half from the larger half. The median is then read off the elements adjacent to the cut, with the exact reading depending on whether the total count is even or odd.
So the search is not for a value. It is for a place to cut.
Why it works
Two cuts, one degree of freedom
Here is the observation that makes it a binary search. Once you choose how many elements the first array contributes to the left part, the second array's contribution is forced, because the two must add to half the total.
That leaves exactly one number to search over: how much the first array contributes, ranging from none of it to all of it. One number, a monotone correctness condition, and the template applies.
Why it works
When is a cut correct?
Name the four elements around the cuts: the last element left of the cut in each array, and the first element right of the cut in each array.
The cut is correct when each array's left-side element does not exceed the other array's right-side element. Within one array that is automatic because it is sorted, so only the two cross-comparisons matter.
If the first array's left element is too big, it contributed too much, so cut it further left. If the second array's is too big, the first array contributed too little. That is the direction rule, and it is what makes the search monotone.
Tip
The infinities are doing real work
A cut can legitimately take nothing from an array or all of it, and then one of the four elements does not exist. Substituting negative infinity for a missing left element and positive infinity for a missing right element makes those cases satisfy the comparisons automatically.
Without the sentinels every comparison needs a guard and the function triples in length. This is the same tidiness idea as the zero-height sentinel bar in Unit 4: invent a value that makes the boundary case behave like the ordinary one.
Gotcha
Search the shorter array
Run the binary search over the shorter of the two arrays. If you search the longer one, the forced contribution from the shorter one can come out negative or larger than that array, and you need extra clamping to avoid indexing errors.
Swapping at the top so the first array is always the shorter one costs one line and removes a whole class of edge cases. The complexity becomes O(log(min(n, m))), which is also the better thing to be able to state.
Edge cases
Reading the answer off the cut
With an odd total, one side holds one extra element and the median is the largest element on that side. With an even total it is the average of the largest on the left and the smallest on the right.
Decide which side you gave the extra element to when you defined half, and stay consistent. Most of the wrong answers on this problem are correct cuts with the final reading done off by one.
This one is genuinely hard
Everything else in this unit is a variation on one template. This problem is that template plus a reframe that most people do not find under time pressure.
Give the merge solution, state its cost, then attempt the cut. Getting partway with a clear explanation of what you are searching for is worth more than a memorized version you cannot justify.
Cost of the partition search
Time and space for the cut-based median, searching over the shorter array, with arrays of length n and m. Answer in terms of the smaller of the two.
Time
Space
Validate a cut
Build the piece the search needs. boundary_values returns the four elements around a cut as (a_left, a_right, b_left, b_right), using infinities where an element does not exist. cut_is_valid reports whether the cut correctly separates the halves. adjust returns "left" if the first array is contributing too much, "right" if too little, and "done" when the cut is valid.
Tests
a, b = [1, 3, 8], [7, 9, 10, 11] print(boundary_values(a, b, 1, 3)) print(boundary_values(a, b, 0, 3)) print(cut_is_valid(a, b, 2, 3), cut_is_valid(a, b, 3, 3)) print(adjust(a, b, 3, 3), adjust(a, b, 2, 3), adjust(a, b, 0, 3))
Output
Run the tests when you are ready.
Median Of Two Sorted Arrays
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.