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.

Say you must eat piles of [4, 9, 6] bananas in at most 5 hours, one pile at a time, at k bananas per hour. A pile of p takes ceil(p / k) hours. What's the slowest k that fits?

Walkthrough

Slowest speed that fits in 5 hours

k123456789hours19107654443<= 5?FFFFTTTTT
Step 1 of 5

Every speed, checked by brute force. Faster never takes longer, so the bottom row flips from F to T exactly once. Binary search finds the flip without filling the table.

mid
ruled out
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 9 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:

Diagram

nums[i] <= nums[-1] in a rotated array

nums45670120123456first runsecond run<= 2?FFFFTTT0123456minimum
first True

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 False everywhere, so there's no boundary and you'd need a special case. nums[-1] always satisfies its own predicate.)

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 row, col = divmod(i, cols).

Diagram

[[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], read row by row

1357101116202330346001234567891011row 0row 1row 2i = 6

With 4 columns, flat index 6 is divmod(6, 4) = (1, 2): row 1, column 2, which holds 16.

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.