DSA Searching

Binary Search

Autocomplete needs the first catalog index whose SKU is not less than MUG-204. A linear scan works at n = 10³. At n = 10⁷ with many queries, the UI stalls unless each lookup pays about log₂ n comparisons.

Binary search is not “keep dividing an array.” It is an -driven boundary finder over a . Sorted lookup is the familiar case; the same proof covers first-true searches on an answer space.

What happens first?

Return contract

Any match, first/last match, or insertion point?

State [lo, hi) and the invariant that the answer still lives there.

Probe mid; discard a half that is provably impossible.

Stop when the interval collapses to the boundary you asked for.

What actually happens

Naive idea: scan left to right until you find the SKU. Correct, and fine for tiny lists. At n = 10⁷ and 100 queries, that is about 10⁹ comparisons: past a typical one-second budget.

Better idea: if the catalog is ordered, one comparison at proves an entire half impossible. Keep an : if the answer exists, it still sits in the remaining interval. Shrink until the interval is empty or the boundary is exact.

The improved design still fails when the data is unsorted, the predicate is not monotone, duplicates need a leftmost index but you return “any”, or lo + hi overflows. Those are not coding nits; they break the proof.

Invariant

After every update, if a valid answer exists, it remains inside the candidate interval. The loop must make strict progress so the interval cannot stall.

How to choose binary search

1. Is the evidence ordered or monotone? If a mid comparison cannot eliminate a whole region, halving is invalid. Sort once, maintain order, or use linear/hash lookup instead.

2. Do you need random access? Midpoint on a linked list costs linear time and erases the log n benefit. Prefer an array or indexed structure.

3. What exact boundary do you need? Any match, , , or an optimum over an answer space? Write that contract before coding the loop.

Quantitative check

log₂(10⁷) ≈ 23. One hundred ordered lookups need roughly 2,300 comparisons after sorting, versus ~10⁹ for naive scans. Sorting alone for a single query is Θ(n log n) and can lose to a linear scan: binary search pays off when order already exists or many queries share it.

When is halving valid?

Ordered evidence

If a[mid] is below the target in ascending data, every earlier value is also too small. A comparison eliminates a whole region, not just one cell.

Random access

The algorithm assumes reaching a midpoint is O(1). On a linked list, repeated midpoint traversal erases the expected benefit.

Stable relation

The ordering or predicate must not change during the search. Concurrent mutation can make already-discarded candidates valid again.

Sorting solely for one lookup costs Θ(n log n), which is more work than a Θ(n) linear scan. Binary search becomes attractive when the data is already ordered, ordering is needed for other reasons, or many queries amortize the preprocessing cost.

Choose one interval convention

Convention	Initial state	Continue while	Typical updates	Empty when
Closed [lo, hi]	lo = 0, hi = n - 1	lo <= hi	lo = mid + 1 / hi = mid - 1	lo > hi
Half-open [lo, hi)	lo = 0, hi = n	lo < hi	lo = mid + 1 / hi = mid	lo == hi

This chapter uses half-open intervals for array boundaries. They compose naturally with slices, permit hi = n, and make interval width exactly hi - lo. The lower-bound answer itself is maintained in the closed boundary range [lo, hi], because an insertion point can equal n.

Exact lookup with a half-open interval

Invariant

If the target exists, at least one occurrence is in [lo, hi). The midpoint belongs to that interval because lo ≤ mid < hi.

If a[mid] < target, sortedness proves indices through mid are too small.
If a[mid] > target, sortedness proves indices from mid onward are too large.
Both continuing branches reduce hi - lo, so the loop must terminate.
An empty interval means no possible occurrence remains.

Python

python

def binary_search(values, target):
    lo, hi = 0, len(values)       # search [lo, hi)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if values[mid] == target:
            return mid            # any matching duplicate
        if values[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return -1

Java

java

final class BinarySearch {
    static int find(int[] values, int target) {
        int lo = 0;
        int hi = values.length; // search [lo, hi)

        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (values[mid] == target) return mid;
            if (values[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return -1;
    }
}

Interactive invariant lab

Step through exact lookup, a duplicate-aware lower bound, and the first feasible point of a false-to-true predicate. Watch the same interval mechanics serve three contracts.

Binary-search invariant laboratory

Watch a half-open interval shrink. Equality, duplicate boundaries, and answer-space search differ only in which half remains possible.

find 9

Step 1 / 3

Active / unresolved

[0, 8)

Interval width

Outcome

keep searching

2[0]

4[1]

4[2]

4[3]

7[4]

9[5]

12[6]

15[7]

lo = 0 · mid = 4 · hi = 8 (hi is excluded)

Decision

7 < 9, so discard indices ≤ 4 and set lo = 5.

Invariant / proof

Every value before index 0 is already too small; the target, if present, is in [0, 8).

Original visualizer · preserved

Interactive binary search demo

Watch the active interval shrink around a target as the midpoint rules out one half at a time.

ℹ️ Ready to Binary Search!

103

404

505

606

707

808

909

Lower bound and upper bound

lower_bound(target)

First index i with a[i] ≥ target

First occurrence, sorted insertion before equals, start of an equal range

upper_bound(target)

First index i with a[i] > target

Insertion after equals, one-past-last occurrence, end of an equal range

values = [1, 2, 2, 2, 5] target = 2
lower_bound = 1 upper_bound = 4 count = 4 - 1 = 3

Lower bound

TypeScript

typescript

function lowerBound(a: readonly number[], target: number): number {
  let lo = 0, hi = a.length;
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (a[mid] < target) lo = mid + 1;
    else hi = mid;                 // equality stays a candidate
  }
  return lo;                       // may equal a.length
}

Java

java

final class LowerBound {
    static int find(int[] values, int target) {
        int lo = 0;
        int hi = values.length;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (values[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid; // equality stays a candidate
            }
        }
        return lo; // may equal values.length
    }
}

Upper bound

TypeScript

typescript

function upperBound(a: readonly number[], target: number): number {
  let lo = 0, hi = a.length;
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (a[mid] <= target) lo = mid + 1; // equality moves right
    else hi = mid;
  }
  return lo;
}

Java

java

final class UpperBound {
    static int find(int[] values, int target) {
        int lo = 0;
        int hi = values.length;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (values[mid] <= target) {
                lo = mid + 1; // equality moves right
            } else {
                hi = mid;
            }
        }
        return lo;
    }
}

First occurrence

i = lower_bound(x); valid iff i < n and a[i] == x

Last occurrence

i = upper_bound(x) - 1; validate i ≥ 0 and a[i] == x

Equal range count

upper_bound(x) - lower_bound(x)

Binary search on the answer

Sometimes candidate answers are numbers rather than stored elements. Define feasible(x) so its results are monotone, for example false, false, false, true, true. Then search for the first true candidate.

Proof obligation: explain why feasibility never flips back. If capacity c can ship all packages within D days, any larger capacity can use the same schedule. That monotonicity, not the word “minimum”: licenses binary search.

Typical problems include minimum machine speed, minimum capacity, maximum tolerable distance, square roots, placement distance, and “can we complete at least k items within budget x?”

Python

python

def minimum_ship_capacity(weights, days):
    def feasible(capacity):
        used_days, load = 1, 0
        for weight in weights:
            if load + weight > capacity:
                used_days += 1
                load = 0
            load += weight
        return used_days <= days

    lo, hi = max(weights), sum(weights)  # answer is in [lo, hi]
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if feasible(mid):
            hi = mid                    # mid may be the minimum
        else:
            lo = mid + 1                # mid is proven impossible
    return lo

Java

java

final class ShippingCapacity {
    static long minimum(int[] weights, int days) {
        if (weights.length == 0 || days <= 0) {
            throw new IllegalArgumentException("nonempty weights and positive days required");
        }

        long lo = 0;
        long hi = 0;
        for (int weight : weights) {
            if (weight < 0) throw new IllegalArgumentException("negative weight");
            lo = Math.max(lo, weight);
            hi += weight;
        }

        while (lo < hi) {
            long mid = lo + (hi - lo) / 2;
            if (feasible(weights, days, mid)) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }

    private static boolean feasible(int[] weights, int days, long capacity) {
        int usedDays = 1;
        long load = 0;
        for (int weight : weights) {
            if (load + weight > capacity) {
                usedDays++;
                load = 0;
            }
            load += weight;
        }
        return usedDays <= days;
    }
}

If the numeric range has width R and one feasibility check costs C, total time is Θ(C log R). For integer domains, establish a known feasible/infeasible boundary and exact endpoint semantics before writing the loop.

Correctness recipe for first-true search

Define

State candidate domain and predicate in one sentence.

Prove monotonicity

Show why false→true has at most one boundary.

Preserve

Prove each branch keeps the boundary in the maintained range.

Terminate

Show an integer measure such as hi - lo decreases to zero.

This recipe separates correctness from syntax. Most binary-search bugs are an unstated boundary contract showing up later as an off-by-one error.

Complexity and real-machine behavior

Worst-case comparisons

Θ(log₂ n)

A midpoint hit is Θ(1) best case; otherwise each update halves the candidate count.

Extra space

Θ(1) iterative

A recursive implementation uses O(log n) call-stack frames in the worst case.

Preprocessing

0 or Θ(n log n)

Zero if order is already maintained; sorting for the search changes the total cost.

Binary search uses few comparisons but jumps through memory, so it does not exploit cache lines as smoothly as a forward scan. On tiny arrays, linear search can win despite its Θ(n) bound. Benchmarks and library implementations decide the crossover; Big-O alone does not.

Failure modes and fixes

Mistake	What breaks	Repair
Unsorted or changing data	The comparison no longer identifies an impossible half.	Sort a snapshot, maintain an ordered index, or use linear/hash lookup.
Returning on equality with duplicates	The returned duplicate is unspecified.	Use lower/upper bound when position among duplicates matters.
Mixing interval conventions	A value is skipped, repeated, or indexed out of bounds.	Write the invariant first and make loop guard, midpoint, and updates match it.
No strict progress	lo or hi can remain unchanged forever.	Every continuing branch must shrink the interval; often lo = mid + 1 or hi = mid.
Unsafe midpoint arithmetic	lo + hi can overflow fixed-width integers.	Use lo + (hi - lo) / 2 (with the language-appropriate floor).
Linked-list input	Finding each midpoint costs linear time.	Use an array/indexed structure, or choose a traversal-native strategy.

Edge cases to trace by hand

Empty input

lo = hi = 0; the loop must not index the array.

One value

Check both matching and missing targets on either side.

All duplicates

Exact search may return any; lower/upper bounds must reach opposite edges.

Target below/above range

Boundary functions should return 0 or n without indexing that insertion point.

Descending order

Reverse every comparison consistently or supply a comparator.

Floating-point answer

Use a fixed iteration count or tolerance; mid may round to an endpoint and stall.

Related patterns

Exponential search

When the upper bound is unknown, probe 1, 2, 4, 8, … until crossing the target, then binary-search the discovered range.

Rotated sorted array

At least one half is normally sorted. Use that fact to decide which region can contain the target; duplicates can destroy decisive comparisons.

Parallel binary search

Batch many monotone offline queries and evaluate their midpoints together. It is an advanced optimization, not the default single-query algorithm.

Implementation checklist

Write the exact return contract: any match, first/last match, insertion point, or optimum.
State the ordering or monotone predicate and prove the direction of elimination.
Choose closed or half-open endpoints and keep every line consistent with that choice.
Compute the midpoint safely and ensure every non-returning branch makes strict progress.
Test empty, singleton, duplicates, missing-below, missing-above, and boundary answers.

Exercises

For [1, 2, 2, 2, 5] and target 2, write both a “any index” loop and a loop. What breaks if you mix half-open updates with a closed loop guard?
n = 2 × 10⁵ already-sorted integers, q = 2 × 10⁵ membership queries. Compare total comparisons for per-query linear scan vs binary search. When would you still prefer a hash set?
Give a counterexample where binary search on a rotated array with duplicates returns the wrong half. What extra check restores a safe branch?

Primary sources

Cormen et al., Introduction to Algorithms (CLRS): binary search and loop invariants.
Stepanov & McJones, Elements of Programming: partition and lower/upper bound on sorted ranges.
C++ std::lower_bound / std::upper_bound documentation (half-open range contracts).

Takeaway

Binary search is an invariant-driven boundary finder. Once you define the candidate interval and monotone decision precisely, exact lookup, duplicate ranges, insertion positions, and optimization over an answer space become variations of the same proof.