Explore binary search interview problems with animated rotated arrays, Koko eating bananas and median examples. Follow the search boundaries step by step.
The pattern
Binary Search: rule out half with every question
If one comparison can tell you which half the answer is in, you can throw the other half away. Repeat, and n candidates shrink to one in about log₂ n steps. The list doesn't even have to exist: any yes/no question whose answer switches once (all no, then all yes) can be binary searched.
1Halve what's left
Looking for 31 in a sorted list: the middle is 16, too small. Everything left of it is even smaller, so half the list is ruled out in one comparison. n numbers take about log₂ n steps.
2Binary search on the answer
There's no list in Koko Eating Bananas, but “is speed k fast enough?” is no for every small k and yes from the answer on. One switch-over is all binary search needs.
3Which half is sorted?
A rotated list isn't sorted, but wherever M lands, one side of it is. Check whether the target fits inside that sorted side; if not, it's on the other side.
How to spot it
- The input is sorted (or sorted with a twist, like a rotation) and you need to find something.
- The problem asks for O(log n).
- “Minimum speed / capacity / time such that …”: binary search on the answer.
- “Latest record at or before t”, “largest value ≤ x”: a search that remembers its last match.
The template (Python)
l, r = lo, hi
while l <= r:
m = (l + r) // 2
if ok(m): # m works: remember it,
best = m # then look for a smaller one
r = m - 1
else:
l = m + 1
return bestThis finds the first m that works (Koko). Exact searches add an early return when nums[m] is the target, and Time Map flips it to find the last m that works. For the basic search on its own, see the Binary Search visualizer.
NeetCode 150 · Binary Search
All 7 problems
Pick a problem to see it solved step by step. They're in NeetCode's order, roughly easiest first.
Binary Search
EasyGiven a sorted list of distinct numbers and a target, return the target's index, or −1 if it isn't there. It must run in O(log n) time.
nums = [-1, 0, 3, 5, 9, 12], target = 9
nums (sorted)
variables
- target
- 9
- L
- 0
- R
- 5
- still possible
- 6
Press Play or Step to watch the solution run.
Brute force vs the pattern
On this input:
- Pattern: O(log n)
- 2 ops
- Brute force
- 5 ops
On a bigger input (200 numbers, target missing):
- Pattern
- 8 ops
- Brute force
- 200 ops
Check every number from the left: up to n comparisons. Binary search needs about log₂ n, which is 8 for 200 numbers and 20 for a million.
“ops” counts basic steps: lookups, inserts, comparisons, array reads. On tiny inputs brute force can even win, because it may stumble on the answer early; as n grows, the gap opens up.
How it works: Binary Search
Step by step
- Middle M
- Ruled out
- Found
Press Start or Step: the step the animation is on lights up below.
- 1
Whole list in range
L = 0, R = n − 1.
l, r = 0, len(nums) - 1 - 2
Middle too small → go right
Rule out M and everything left of it.
if nums[m] < target: l = m + 1 - 3
Middle too big → go left
Rule out M and everything right of it.
elif nums[m] > target: r = m - 1 - 4
Middle equals target → return M
Found.
else: return m - 5
L > R → −1
The range is empty.
return -1
Look at the middle value. If it's too small, the target can only be to its right, because the list is sorted, so the whole left half is ruled out in one comparison. If it's too big, rule out the right half.
Each comparison halves what's left, so n numbers need only about log₂ n comparisons. Stop when you find it, or when L passes R and nothing is left.
Spot it in an interview
- The data is sorted, or you can ask a yes/no question whose answer flips once (all “no” then all “yes”).
- “O(log n)” in the problem statement almost always means binary search.
The range halves on every comparison.
Credits
Learn more from NeetCode
The problem list and order come from the NeetCode 150 by NeetCode (neetcode.io). The solutions here follow the approaches NeetCode teaches in the linked videos; the animations, explanations and code were written for CodeQuest. If these help, NeetCode's videos and site are well worth your time.
Problem statements are summarised in our own words; the full versions are on LeetCode.