Search the Answer, Rotations and Grids

Binary Search, lesson 3 of 3

Search the Answer, Rotations and Grids

Binary search over a range of answers, rotated sorted arrays, and 2D matrices as 1D.

14 min, 0 of 4 activities solved

View cheatsheet

Getting Python ready… examples can run in a moment.

Binary search on the answer. Sometimes there's no array to search at all. The question is "what's the smallest X that works?" (or the largest), and you can cheaply check any single candidate:

speed k:        1  2  3  4  5  6 ...
can finish(k)?  F  F  F  T  T  T ...
                         ^ answer

If making X bigger never turns a "yes" into a "no", the check is monotonic and you can binary-search the range of answers with the same template:

  1. Write can(x) -> bool, usually a greedy O(n) pass.
  2. Pick lo = smallest conceivable answer and hi = one you know works.
  3. Find the first x with can(x).

Cost: O(n log R), where R is the size of the range. Even R = 10^9 is only ~30 checks.

Classic phrasings: minimise the maximum (split an array, ship packages), smallest speed / capacity / days, maximise the minimum (distance between cows, piece length).

Example

Maximise: longest equal pieces from ropes

This is a maximise problem, so we searched for the first length that fails and stepped back. Only 10 checks for lengths 1..803; the brute force would try up to 802 lengths. Change k to 100 and watch the answer shrink.

Quiz

You must split an array into k parts minimising the largest part sum. What range do you binary-search?

Rotated sorted arrays. Take a sorted array and rotate it: [0, 1, 2, 4, 5, 6, 7] becomes [4, 5, 6, 7, 0, 1, 2]. It's two sorted runs, and every value in the second run is <= the last element, while every value in the first run is bigger. That's a monotonic predicate:

nums:              4  5  6  7  0  1  2
nums[i] <= nums[-1] F  F  F  F  T  T  T
                                ^ minimum

The first True is the minimum (the rotation point). Once you know it, target search is an ordinary lower bound inside whichever run could hold the target: target <= nums[-1] means the right run, otherwise the left one.

(Compare with nums[-1], not nums[0]: if the array isn't rotated at all, nums[i] >= nums[0] is True everywhere and the boundary vanishes.)

Example

Find the rotation point

Here hi = len(nums) - 1, not len(nums): the last element always satisfies the predicate, so "none" is impossible and we save a step.

Quiz

For nums = [6, 7, 1, 2, 3, 4, 5], what does the predicate nums[i] <= nums[-1] look like?

A sorted matrix is a sorted list in disguise. If each row is sorted and each row starts after the previous one ends, reading the rows left to right gives one sorted list of rows * cols values. Search indexes 0 .. rows*cols and turn each index back into a cell with divmod:

 1  3  5  7        0  1  2  3
10 11 16 20   <->  4  5  6  7
23 30 34 60        8  9 10 11

row, col = divmod(i, cols)

No copying, O(log(rows * cols)) time, O(1) space.

Quiz

What does this print?

Exercise

Integer square root

Write int_sqrt(n) returning the largest integer x with x * x <= n (for n >= 0), using binary search on the answer. No math.sqrt, math.isqrt or ** 0.5.

Think of it as "first x with x * x > n, minus 1". It has to be fast even for n = 10**18.