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.

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.

1def cut_is_valid(a, b, take_from_a, half):2    """take_from_a elements of a and the rest of half from b go left."""3    take_from_b = half - take_from_a4    NEG, POS = float("-inf"), float("inf")5 6    a_left = a[take_from_a - 1] if take_from_a > 0 else NEG7    a_right = a[take_from_a] if take_from_a < len(a) else POS8    b_left = b[take_from_b - 1] if take_from_b > 0 else NEG9    b_right = b[take_from_b] if take_from_b < len(b) else POS10 11    return a_left <= b_right and b_left <= a_right12 13a, b = [1, 3, 8], [7, 9, 10, 11]14print(cut_is_valid(a, b, 2, 3), cut_is_valid(a, b, 3, 3))

Taking 2 from a and 1 from b puts 1, 3, 7 on the left and 8, 9, 10, 11 on the right

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.

Complexity· 5 min

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.

Python

1low, high = 0, len(shorter)2while low <= high:3    take_from_shorter = (low + high) // 24    take_from_longer = half - take_from_shorter5    # four boundary elements, two comparisons, adjust low or high6    ...

Code lab· 30 min

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.

solution.py

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 tests to see output.

Problem· 40 min

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.

CodeGround