Binary Search
Halve a search space every step: the lower-bound template, boundary pitfalls, and searching on the answer instead of an array.
beginner40 min#binary-search#lower-bound#search-on-answer#invariants
Prerequisites: Arrays and Dynamic Arrays, Big-O and Complexity Analysis
Why it matters
Binary search turns 1,000,000,000 candidates into about 30 checks. It is the reason sorted data and database indexes are so valuable, and it is one of the most error-prone short algorithms: a famous bug in a widely used library implementation went unnoticed for years. Beyond arrays, the idea of "discard half the possibilities with one yes or no question" solves optimization problems where you can test whether a given answer is good enough.
Intuition
Guess a number between 1 and 100 where each guess is answered "too low" or "too high". Guess 50; if it is too low, everything from 1 to 50 is eliminated. Seven guesses are enough for 100 numbers, because each one halves what remains (2^7 = 128).
The payoff is easiest to see by counting worst-case checks. Note the log scale: linear search grows a thousandfold at each step, while binary search adds about 10 checks.
The requirement is monotonicity: the answers must flip from "no" to "yes" exactly once, like F F F F T T T T. Sorted arrays have this shape for the question "is a[i] >= target?". Once you see the problem as finding the first T in a monotone row, binary search applies even when there is no array at all.
How it works
Use one template and learn it well. It finds the first index where a condition is true, searching the half-open range [lo, hi):
lo = 0, hi = n the answer is in [lo, hi]; hi = n means "none"
while lo < hi:
mid = lo + (hi - lo) // 2
if condition(mid): hi = mid # mid could be the answer, keep it
else: lo = mid + 1 # mid is definitely not, drop it
return lo
Here is the template running as lower bound on [1, 2, 2, 2, 5, 8] with target 3, a not-found case. The green cell is mid, and faded cells have been discarded. When hi is 6 it sits past the end of the array, so no arrow is drawn for it.
Each check discards half of what remains. Lower bound always returns a position, so you must still test a[lo] == target to know if the value exists.
Why this is safe:
- Invariant: the first true position is always within
[lo, hi]. Each branch preserves it and strictly shrinks the range, so the loop ends. - No infinite loop:
midis always less thanhiwhenlo < hi, andlo = mid + 1always makes progress. - Overflow:
lo + (hi - lo) // 2avoids(lo + hi)overflowing in languages with fixed-size integers. Python and JavaScript numbers do not overflow here, but the habit is free.
With condition(i) = a[i] >= target this is lower bound (first position where target could be inserted). With a[i] > target it is upper bound. A value exists if lower bound is in range and a[lo] == target. The count of a value is upper_bound - lower_bound; our code computes it as lower_bound(x + 1) - lower_bound(x) for integers.
Search on the answer. Suppose you want the smallest capacity, speed or time that makes something feasible. Write feasible(x), which is false for small x and true from some point on. The search range is the possible answers, not array indexes: the lowest sensible answer and a value that is certainly enough. In the example below, packages must be shipped in order in days days; capacity can be no smaller than the heaviest package and never needs to exceed the total weight. Each feasible check is a greedy O(n) pass.
For the shipping example (weights 1 to 10, 5 days), the search range is capacities 10 to 55. Each row below is one loop iteration; capacity 15 is the first feasible one.
Search on the answer: the same lo/hi/mid loop, but the 'array' is the range of possible capacities and the test is feasible().
| Operation | Time | Notes |
|---|---|---|
| Binary search on sorted array | O(log n) | Needs random access |
| Search on the answer | O(n log R) | R = size of the answer range, n = cost of feasible() |
| Linear search | O(n) | Works on unsorted data |
| Sort first, then search | O(n log n) | Only worth it for many queries |
Code: lower bound, counting, and minimum ship capacity
def lower_bound(a, target):
"""First index i with a[i] >= target (len(a) if none)."""
lo, hi = 0, len(a) # answer lies in [lo, hi]
while lo < hi:
mid = lo + (hi - lo) // 2
if a[mid] < target:
lo = mid + 1 # mid is too small, discard it
else:
hi = mid # mid might be the answer, keep it
return lo
def count_in_range(a, x):
return lower_bound(a, x + 1) - lower_bound(a, x)
def min_capacity(weights, days):
"""Smallest ship capacity that moves all packages in order within `days`."""
def feasible(cap):
used, load = 1, 0
for w in weights:
if load + w > cap:
used += 1
load = 0
load += w
return used <= days
lo, hi = max(weights), sum(weights) # answer is somewhere in here
while lo < hi:
mid = lo + (hi - lo) // 2
if feasible(mid):
hi = mid
else:
lo = mid + 1
return lo
a = [1, 2, 2, 2, 5, 8]
print(lower_bound(a, 2), lower_bound(a, 3), lower_bound(a, 9))
print(count_in_range(a, 2))
print(min_capacity([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5))// First index i with a[i] >= target (a.length if none).
function lowerBound(a, target) {
let lo = 0;
let hi = a.length; // answer lies in [lo, hi]
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (a[mid] < target) lo = mid + 1; // mid is too small, discard it
else hi = mid; // mid might be the answer, keep it
}
return lo;
}
const countInRange = (a, x) => lowerBound(a, x + 1) - lowerBound(a, x);
// Smallest ship capacity that moves all packages in order within `days`.
function minCapacity(weights, days) {
const feasible = (cap) => {
let used = 1;
let load = 0;
for (const w of weights) {
if (load + w > cap) {
used++;
load = 0;
}
load += w;
}
return used <= days;
};
let lo = Math.max(...weights); // answer is somewhere in [lo, hi]
let hi = weights.reduce((s, w) => s + w, 0);
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (feasible(mid)) hi = mid;
else lo = mid + 1;
}
return lo;
}
const a = [1, 2, 2, 2, 5, 8];
console.log(lowerBound(a, 2), lowerBound(a, 3), lowerBound(a, 9));
console.log(countInRange(a, 2));
console.log(minCapacity([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5));Both versions print:
1 4 6
3
15
For [1, 2, 2, 2, 5, 8], the first position of 2 is 1, the first position where something >= 3 could go is 4, and 9 would go at the end (index 6). There are 3 twos. For the weights 1 to 10 shipped within 5 days, the smallest capacity is 15 (days of 1 to 5, then 6 and 7, then 8, then 9, then 10 fit exactly in five days with capacity 15, while capacity 14 would need six).
Common pitfalls
- Infinite loop:
lo = midwithmid = (lo + hi) // 2never advances whenhi = lo + 1. Uselo = mid + 1or roundmidup in that variant. - Wrong initial bounds: for search on the answer, a lower bound that is too high excludes the true answer. Think about the extreme cases.
- Running on unsorted or non-monotone data: the result is silent garbage. Verify the "F then T" shape first.
- Duplicates: classic "find the target" returns any match. If you need the first or last, use lower or upper bound.
- Floating point answers: loop a fixed number of iterations (for example 60) instead of testing
lo == hi, and decide the precision you need. - Using the built-in wrong: Python's
bisect_leftandbisect_rightcorrespond to lower and upper bound; JavaScript has no built-in, so write the template once.
Practice
Search insert position easy
Hint
This is exactly lower bound.
Show solution
Return the first index i with a[i] >= target, which is also where the target should be inserted to keep the array sorted. Use the template above with hi = n. O(log n).
First and last position of a value medium
Hint
Two searches with slightly different conditions.
Show solution
First position is lower_bound(target). Last position is lower_bound(target + 1) - 1 for integers (or an upper bound with a[i] > target). If the first position is out of range or a[first] != target, the value is absent. O(log n) total.
Search in a rotated sorted array medium
Hint
At any midpoint, at least one half is properly sorted. Can you tell which and check whether the target lies in it?
Show solution
Compare a[lo] and a[mid] to find the sorted half. If the target lies within that half's range, search there; otherwise search the other half. Each step discards half the range, so O(log n). Take care with <= versus < at the boundaries when elements are distinct.
Koko eats bananas (minimum speed) hard
Hint
If speed k finishes in time, will any larger speed also finish? What are the smallest and largest sensible speeds?
Show solution
Search k from 1 to max(piles). feasible(k) sums ceil(pile / k) over all piles and checks that the hours are at most h. It is monotone, because a faster speed never takes longer. Find the first feasible k with the template. O(n log max). The same pattern solves splitting arrays, painting fences and placing routers.
Interview questions
- Why must the data be sorted? The algorithm discards half the range based on one comparison, which is only valid if the comparison outcome is monotone across the range.
- What is the loop invariant? The answer, if it exists, always lies within the current range; each step keeps that true and shrinks the range.
- How do you recognize a search-on-answer problem? The question asks for the minimum or maximum value of something, and you can check any candidate quickly with a yes or no test that is monotone.
- Why compute mid as
lo + (hi - lo) / 2? To avoid integer overflow in fixed-width languages.
Interviewers look for: stating the invariant, testing the one-element, empty and not-found cases aloud, and explaining why the answer range bounds are right.
Quick check
You run the lower-bound template on [1, 2, 2, 2, 5, 8] with target 6. What does it return?
Finished this lesson?
Further resources
- Binary search algorithm (Wikipedia) (article)
- Python docs: bisect (docs)