Pattern Guide
Binary Search
"Eliminate half the search space every step."
Binary search is not just for sorted arrays. The real insight is "binary search on the answer" — any monotonic yes/no predicate can be binary searched. Learn classic BS, BS on answer, and rotated array tricks.
Problems you can solve with this pattern
11 problems · click any to start solving
let left = 0, right = n - 1;
while (left <= right) {
const mid = (left + right) >> 1;
if (arr[mid] === target) return mid;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;Binary search is one of the most misunderstood patterns. Beginners think it's only for "find x in sorted array." But the real power is binary search on the ANSWER: whenever you can write a monotonic predicate isValid(x) — where all false values come before all true values — you can binary search the answer space and find the boundary in O(log n).
1. Classic — find a value in sorted array
2. Find boundary — find leftmost/rightmost position where condition changes
3. Search on answer — the search space is a range of possible answers, not the array itself
When to Reach for Binary Search on Answer
| Signal | What It Means |
|---|---|
| "minimum maximum" or "maximum minimum" | Binary search on the answer value |
| "is it possible with k operations?" | Write isValid(k), binary search on k |
| "at least / at most k" | Binary search on k with a greedy feasibility check |
| Monotonic feasibility | If valid(x) then valid(x+1), binary search the boundary |
| Sorted array — find first/last | Find boundary, not just any match |
| Rotated sorted array | One half is always sorted, use that half to decide direction |
Core Templates
let left = 0, right = n - 1;
while (left <= right) {
const mid = (left + right) >> 1;
if (arr[mid] === target) return mid;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;// All false values come BEFORE all true values.
// Find first index where isTrue(arr[mid]) flips to true.
let left = 0, right = n - 1, ans = -1;
while (left <= right) {
const mid = (left + right) >> 1;
if (isTrue(arr[mid])) {
ans = mid; // candidate — but check if there's an earlier one
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;// isValid(mid): can we achieve it with at most mid resources?
// Returns minimum k where isValid(k) is true.
let left = minPossible, right = maxPossible;
while (left <= right) {
const mid = (left + right) >> 1;
if (isValid(mid)) right = mid - 1; // could be smaller
else left = mid + 1; // too small, need more
}
return left; // first value where isValid is trueBinary search on answer + difference array. Classic "minimum k queries" pattern.
Variation Trick
The isValid Pattern — Same Template, Different Predicate
Base template
let left = lowerBound, right = upperBound;
while (left <= right) {
const mid = (left + right) >> 1;
if (isValid(mid)) right = mid - 1; // ← just change isValid()
else left = mid + 1;
}
return left;Change only one line to solve:
Minimum days to make m bouquets
More days = more flowers bloomed = easier to make bouquets → monotonic
Capacity to ship packages within D days
Higher capacity = fewer days needed → monotonic
Split array largest sum
Higher maxSum = fewer pieces needed → monotonic
- Sorted array, find target → standard lo/hi
- Rotated sorted array → check which half is sorted
- Find peak/min → compare mid with neighbor, go toward larger
- "Minimize maximum" / "Maximize minimum" → binary search on answer
- Two sorted arrays, find median → binary search on partition
"Binary search on answer" template:
1. Identify: monotone feasibility function f(x) — if x works, x+1 also works (or vice versa)
2. Set lo/hi to range of valid answers
3. Check if mid is feasible (greedy simulation)
4. Move lo/hi based on feasibility
Common "binary search on answer" problems: Koko, Ship Packages, Split Array, Minimum Effort Path.