Binary search: how to spot it
We'll cover the following
If one check tells you whether the answer is to the left or the right, you can discard half of the options every step. A billion items takes about 30 steps.
How the question sounds
- Sorted array and an O(log n) requirement
- A rotated sorted array
- Find the first or last position where something becomes true
- Minimum speed, capacity or days such that it is possible: search on the answer
- A yes/no check that flips from no to yes exactly once
The two shapes
Where it shows up in GenAI work
Finding the largest batch size or context length that fits in GPU memory, or the lowest threshold that still passes an eval, is a binary search on the answer.
Is it binary search?
Decide yes or no before you open each answer.
Check yourselfFind a target in a sorted array in O(log n).
Yes. Sorted and log n is the textbook case.
Check yourselfFind the minimum eating speed so Koko finishes all piles in h hours.
Yes. Speeds are ordered and feasibility flips once, so search on the answer.
Check yourselfFind the smallest element in a rotated sorted array.
Yes. Compare mid with the right end to know which half holds the break.
Check yourselfFind two numbers in a sorted array that add up to a target.
No. Two pointers from both ends do this in O(n) with no guessing.
Check yourselfCount how many times each word appears.
No. Counting is a hash map job.
Check yourselfFind the longest substring without repeats.
No. A moving range, so sliding window.
Problems in this pattern
- Binary search · Easy · Find a value
- First value at least target · Easy · Find a boundary
- Search in a rotated array · Medium · Half is sorted
- Slowest eating speed · Medium · Search on the answer
Summary: say it in the interview
- On the array: Compare the middle value with the target and keep the half that can still contain it.
- On the answer: Guess a value, test whether it works, and use the result to move the range of guesses.