DevPath
Tracks

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.

Linear, 1,000 items
1,000 checks
Binary, 1,000 items
10 checks
Linear, 1,000,000 items
1,000,000 checks
Binary, 1,000,000 items
20 checks
Linear, 1,000,000,000 items
1,000,000,000 checks
Binary, 1,000,000,000 items
30 checks
Worst-case number of comparisons (log scale). A billion items still need only about 30 binary-search 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.

1
0
lo
2
1
2
2
2
3
5
4
8
5
Start: lo = 0, hi = 6 (one past the end, meaning none). The first index with a value of at least 3 is somewhere in [0, 6].
step 1 / 5

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: mid is always less than hi when lo < hi, and lo = mid + 1 always makes progress.
  • Overflow: lo + (hi - lo) // 2 avoids (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.

lohimidfeasible(mid)?
start
10
55
The answer lies between the heaviest package (10) and the total weight (55).
step 1 / 7

Search on the answer: the same lo/hi/mid loop, but the 'array' is the range of possible capacities and the test is feasible().

OperationTimeNotes
Binary search on sorted arrayO(log n)Needs random access
Search on the answerO(n log R)R = size of the answer range, n = cost of feasible()
Linear searchO(n)Works on unsorted data
Sort first, then searchO(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))

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 = mid with mid = (lo + hi) // 2 never advances when hi = lo + 1. Use lo = mid + 1 or round mid up 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_left and bisect_right correspond 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

  1. 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.
  2. 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.
  3. 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.
  4. 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

Related lessons