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 cheatsheetGetting 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?
Slowest speed that fits in 5 hours
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.
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:
- Write
can(x) -> bool, usually a greedy O(n) pass. - Pick
lo= smallest conceivable answer andhi= one you know works. - Find the first
xwithcan(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).
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.
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[i] <= nums[-1] in a rotated array
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.)
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.
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).
[[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], read row by row
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.
What does this print?
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.