Overview
Binary search finds a target in a sorted array by repeatedly comparing with the middle element and discarding the half that cannot contain it. Thirty comparisons are enough for a billion elements. The idea is simple; the implementation is famously easy to get subtly wrong at the boundaries.
The bigger idea is that binary search works on any monotonic predicate — a yes/no question whose answer switches from "no" to "yes" exactly once. "Can Koko finish all bananas at speed k?" is false for small k and true for large k, so you can binary search on k itself. This "binary search on the answer" pattern solves many optimisation problems that look nothing like searching.
Key concepts
Tick a concept once you can explain it in your own words without notes.
Complexity cheat sheet
| Operation | Cost |
|---|---|
| Search in sorted array | O(log n) |
| Binary search on answer | O(log(range) × cost of feasibility check) |
| Lower/upper bound | O(log n) |
Patterns to recognise
Exact match
Use it for: Classic search in a sorted array.
Return when a[mid] equals the target; otherwise discard a half.
First true
Use it for: First bad version, lower bound, search insert position.
If ok(mid), record and go left (hi = mid − 1); else go right.
Minimise the maximum
Use it for: Ship packages in D days, split array largest sum, Koko eating bananas.
Binary search the answer value; check feasibility greedily in O(n).
Code template
def first_true(lo, hi, ok):
"""Smallest x in [lo, hi] with ok(x) True; returns hi + 1 if none."""
while lo <= hi:
mid = lo + (hi - lo) // 2
if ok(mid):
hi = mid - 1
else:
lo = mid + 1
return lo
def min_eating_speed(piles, h):
def can_finish(k):
return sum((p + k - 1) // k for p in piles) <= h
return first_true(1, max(piles), can_finish)
template <class Pred>
long long firstTrue(long long lo, long long hi, Pred ok) {
while (lo <= hi) {
long long mid = lo + (hi - lo) / 2;
if (ok(mid)) hi = mid - 1;
else lo = mid + 1;
}
return lo; // hi + 1 if none
}
int minEatingSpeed(const vector<int>& piles, int h) {
auto canFinish = [&](long long k) {
long long hours = 0;
for (int p : piles) hours += (p + k - 1) / k;
return hours <= h;
};
int maxPile = *max_element(piles.begin(), piles.end());
return (int)firstTrue(1, maxPile, canFinish);
}
Common mistakes
- Mixing conventions (inclusive hi with
<, or lo = mid with an exclusive bound) is the source of most infinite loops. - The predicate must be truly monotonic; otherwise binary search returns garbage silently.
- Test with arrays of size 1 and 2, and with the target at both ends.
Quick check
Three questions on Binary Search. Get all three right to earn +15 XP.
-
What must be true for binary search to work?
Each comparison must let you safely discard half of the space.
-
Why write mid = lo + (hi - lo) / 2 instead of (lo + hi) / 2?
For large indices lo + hi can exceed the integer range in C++ or Java.
-
"Binary search on the answer" applies when:
If feasible(x) is false, false, ..., true, true, you can binary search for the boundary.
Challenges
Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.
- Binary SearchLeetCode Easy +20
- Search Insert PositionLeetCode Easy +20
- First Bad VersionLeetCode Easy +20
- Find First and Last Position of Element in Sorted ArrayLeetCode Medium +40
- Search in Rotated Sorted ArrayLeetCode Medium +40
- Find Minimum in Rotated Sorted ArrayLeetCode Medium +40
- Koko Eating BananasLeetCode Medium +40
- Median of Two Sorted ArraysLeetCode Hard +70
Stuck on Binary Search?Ask Orbi for a hint, a fresh explanation or a review of your code.
Ask the tutor