Why We Need Binary Search & How to Think About It
If you are searching for a name in a physical phonebook of 1,000,000 pages, you don't start at page 1 and read line-by-line (which is linear search, $O(n)$). Instead, you open to the middle, check if your name comes before or after, and discard 500,000 pages in a single second. You repeat this until you find the name. This is Binary Search. It reduces search time from $O(n)$ to $O(\log n)$. For 1,000,000 elements, it takes at most 20 comparisons.
The superpower of binary search is that each query throws away half the remaining search space.
The Monotonicity Rule (When to Use it)
To use binary search, the search space must be monotonic (orderly).
- Sorted Array: Hitting a value too large tells you everything to the right is also too large.
- Answer Space: If a shipping capacity of 10 tons works to deliver packages on time, any capacity larger than 10 tons will also work. If 5 tons is too small, any capacity smaller than 5 tons is also too small. This forms a sorted
False...False | True...Trueboundary, which we can binary-search!
Watch it run
Step through the search: each comparison throws away half the remaining space. Change the array and target, or scrub backwards if a step went by too fast.
1/7Search space is the whole array. Looking for 38.
A template you won't get wrong
Use a half-open [lo, hi) and converge on the first index that satisfies a
predicate. This one template handles "find x", "lower bound", "first true".
# Python
def lower_bound(a, target):
lo, hi = 0, len(a) # half-open [lo, hi)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < target: # predicate: "too small"
lo = mid + 1
else:
hi = mid # mid might be the answer → keep it in range
return lo # first index with a[i] >= target
// Java
public int lowerBound(int[] a, int target) {
int lo = 0, hi = a.length; // half-open [lo, hi)
while (lo < hi) {
int mid = lo + (hi - lo) / 2; // avoid overflow
if (a[mid] < target) { // predicate: "too small"
lo = mid + 1;
} else {
hi = mid; // mid might be the answer
}
}
return lo; // first index where a[i] >= target
}
// C++
#include <vector>
int lowerBound(const std::vector<int>& a, int target) {
int lo = 0, hi = a.size(); // half-open [lo, hi)
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] < target) { // predicate: "too small"
lo = mid + 1;
} else {
hi = mid; // mid might be the answer
}
}
return lo; // first index where a[i] >= target
}
The invariant: everything < lo fails the predicate, everything >= hi
satisfies it. The loop shrinks the unknown region until lo == hi.
The real SDE2 skill: binary search on the answer
When the answer is a number and "does value x work?" is monotonic (if x
works, so does every larger/smaller x), binary-search the answer, not an
array.
# Python — Min ship capacity to deliver all packages in <= D days.
def min_capacity(weights, D):
def feasible(cap):
days, cur = 1, 0
for w in weights:
if cur + w > cap: days, cur = days + 1, 0
cur += w
return days <= D
lo, hi = max(weights), sum(weights) # capacity search space
while lo < hi:
mid = (lo + hi) // 2
if feasible(mid): hi = mid # works → try smaller
else: lo = mid + 1 # doesn't → go bigger
return lo
// Java — Min ship capacity to deliver all packages in <= D days.
public int minCapacity(int[] weights, int D) {
int maxWeight = 0;
int sumWeight = 0;
for (int w : weights) {
maxWeight = Math.max(maxWeight, w);
sumWeight += w;
}
int lo = maxWeight, hi = sumWeight;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (feasible(weights, D, mid)) {
hi = mid; // works → try smaller
} else {
lo = mid + 1; // doesn't → go bigger
}
}
return lo;
}
private boolean feasible(int[] weights, int D, int cap) {
int days = 1, cur = 0;
for (int w : weights) {
if (cur + w > cap) {
days++;
cur = 0;
}
cur += w;
}
return days <= D;
}
// C++ — Min ship capacity to deliver all packages in <= D days.
#include <vector>
#include <numeric>
#include <algorithm>
bool feasible(const std::vector<int>& weights, int D, int cap) {
int days = 1, cur = 0;
for (int w : weights) {
if (cur + w > cap) {
days++;
cur = 0;
}
cur += w;
}
return days <= D;
}
int minCapacity(const std::vector<int>& weights, int D) {
int max_w = *std::max_element(weights.begin(), weights.end());
int sum_w = std::accumulate(weights.begin(), weights.end(), 0);
int lo = max_w, hi = sum_w;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (feasible(weights, D, mid)) {
hi = mid; // works → try smaller
} else {
lo = mid + 1; // doesn't → go bigger
}
}
return lo;
}
"Minimum/maximum X such that a condition holds", "smallest capacity / largest minimum / fastest speed" + a monotonic feasibility check ⇒ binary search on the answer. Complexity is O(n log(range)) — the log of the value range, not the array length.
1. An array has 1,000,000 sorted elements. Roughly how many comparisons does binary search need in the worst case?
2. In the half-open template ([lo, hi), while lo < hi), why is `hi = mid` safe but `lo = mid` an infinite-loop bug?
3. “Minimum ship capacity to deliver all packages within D days” is solved with binary search because…
4. In “Search in Rotated Sorted Array”, the key fact that lets binary search still work is:
Think it through
The page showed binary search on an answer space. Now the other famous twist: searching an array that's sorted but rotated. The trick is finding the half you can still trust. Think before revealing.
PROBLEMA sorted array of distinct values was rotated at an unknown pivot: nums = [4,5,6,7,0,1,2]. Return the index of target, or -1. Required: O(log n).
- 1
Restate & edges
“Why can't I use the plain template, and what's the speed bar?”
- 2
Brute force first
“What's the baseline, and why must I do better?”
unlocks after the stage above - 3
Find the pattern
“Look at mid. The rotation breaks the order in ONE place — so what's always true about the two halves?”
unlocks after the stage above - 4
Code the template
“Once I know the left half is sorted, what's the exact range test for target?”
unlocks after the stage above - 5
Cost & edge check
“Cost, and trace finding 0 in [4,5,6,7,0,1,2]?”
unlocks after the stage above
// Java — Search in Rotated Sorted Array
public int search(int[] nums, int target) {
int lo = 0, hi = nums.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[lo] <= nums[mid]) { // left half is sorted
if (nums[lo] <= target && target < nums[mid]) {
hi = mid - 1; // target is in the sorted left
} else {
lo = mid + 1;
}
} else { // right half is sorted
if (nums[mid] < target && target <= nums[hi]) {
lo = mid + 1; // target is in the sorted right
} else {
hi = mid - 1;
}
}
}
return -1;
}
// C++ — Search in Rotated Sorted Array
#include <vector>
int search(const std::vector<int>& nums, int target) {
int lo = 0, hi = nums.size() - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[lo] <= nums[mid]) { // left half is sorted
if (nums[lo] <= target && target < nums[mid]) {
hi = mid - 1; // target is in the sorted left
} else {
lo = mid + 1;
}
} else { // right half is sorted
if (nums[mid] < target && target <= nums[hi]) {
lo = mid + 1; // target is in the sorted right
} else {
hi = mid - 1;
}
}
}
return -1;
}
Practice — climb the ladder
Binary search needs ONE thing: a monotonic yes/no boundary. The ladder moves from searching arrays to searching ANSWER SPACES — the big leap.
Climb in order — every rung assumes the one above it. Solve on LeetCode, then tick it here; progress is saved on this device.
Warm-up
bounds discipline — no off-by-ones, ever- Binary SearchEasy
The template itself — lo/hi/mid until your invariant survives any input.
Lower bound — WHERE the boundary lands when the target is absent.
Core
broken invariants and first/last boundariesTwo boundary searches (leftmost + rightmost) — bias the mid correctly.
One half is always sorted — decide which, then discard the other.
Searching for a PROPERTY (the pivot), not a value.
- Koko Eating BananasMedium
Binary search ON THE ANSWER — guess a speed, check feasibility, halve.
Same answer-space pattern — min capacity whose check passes.
Stretch
the two famous finalsAnswer-space search where the check is itself greedy — two patterns stacked.
Partition search across two arrays — the hardest classic binary search.