Skip to main content

Binary Search

Binary search speeds up a search by repeatedly halving the active interval. The classic use is looking up a value in a sorted array, but the same split idea powers lower/upper bounds, “binary search on the answer,” continuous root finding, and jump searches on trees.

This lesson follows CP-Algorithms — Binary Search.

Search in sorted arrays​

Given a sorted array A₀ ≤ A₁ ≤ … ≤ Aₙ₋₁, is k present?

Linear scan is O(n) and ignores sortedness. Binary search keeps indices L < R with A_L ≤ k ≤ A_R (so if k appears at all, it lies in that range). Pick a midpoint M with L < M < R:

  • if A_L ≤ k ≤ A_M → shrink to [L, M]
  • if A_M ≤ k ≤ A_R → shrink to [M, R]

When R = L + 1, compare against the two endpoints. In the worst case you always keep the larger half, so choose

M ≈ (L + R) / 2

to minimize max(M−L, R−M). Each step halves the gap; after h steps (R−L) / 2ʰ ≈ 1, so h ∈ O(log n).

For n ≈ 10⁶ ≈ 2²⁰ that is ~20 probes instead of a million.

Lower bound and upper bound​

Often you want:

  • lower bound of k — first index with Aᵢ ≥ k
  • upper bound of k — first index with Aᵢ > k

Together they form the half-open range of elements equal to k. Presence check: find the lower bound and test equality.

Implementation (half-open invariant)​

Maintain L < R with A_L ≤ k < A_R. The active interval is [L, R).

Sentinels: L = -1, R = n, imagining A_{-1} = −∞ and A_n = +∞. Never read A_L or A_R while they are sentinels. Midpoint:

m = ⌊(L + R) / 2⌋
// a[0..n) sorted
int l = -1, r = n;
while (r - l > 1) {
    int m = l + (r - l) / 2; // safer than (l+r)/2
    if (k < a[m]) {
        r = m; // a[l] ≤ k < a[m] ≤ a[r]
    } else {
        l = m; // a[l] ≤ a[m] ≤ k < a[r]
    }
}
// l = last index with a[l] ≤ k (or -1)
// r = first index with a[r] > k (or n)  → upper bound
Midpoint overflow

(l + r) / 2 can overflow for large positive l and r (infamous JDK bug). Prefer l + (r - l) / 2, or C++20 std::midpoint(l, r).

🧪 Lower / upper bound on a sorted array

Interactive walkthrough​

Step through the half-open search. Watch L / R / m and the invariant a[L] ≤ k < a[R].

Quiz

Binary search on arrays

1 / 4

Worst-case probes for binary search on n sorted elements is…

Pick an answer to see if you are right.

Search on an arbitrary predicate​

Let f : {0,…,n−1} → {0,1} be monotone: f(0) ≤ f(1) ≤ … ≤ f(n−1).

Binary search finds the transition: largest l with f(l)=0 and f(l+1)=1 (if a flip exists). Same skeleton — replace k < a[m] with f(m):

int l = -1, r = n;
while (r - l > 1) {
    int m = l + (r - l) / 2;
    if (f(m)) {
        r = m; // f(l)=0, f(m)=1
    } else {
        l = m; // f(m)=0, f(r)=1
    }
}

Invariant: f(l)=0, f(r)=1 (with sentinels for all-0 / all-1 edge cases).

Useful when evaluating f is expensive — you only pay O(log n) calls.

🧪 Binary search on the answer (minimum capacity)

Binary search on the answer​

When you can only check “is the answer ≥ λ?” with a monotone predicate, binary-search λ.

Example idea: maximize a floored average over long enough subarrays. Checking “average ≥ λ” rewrites as “some subarray of aᵢ − λ has length ≥ x+1 and nonnegative sum” (prefix sums). Binary-search λ over the value domain.

If f is continuous on [L, R] and (w.l.o.g.) f(L) ≤ f(R), intermediate-value theorem says every y ∈ [f(L), f(R)] has some x with f(x)=y. Halve [L, R] by comparing f(M) to y. Accuracy ±δ costs O(log((R−L)/δ)) — no monotonicity required.

Classic: roots of odd-degree polynomials (f → −∞ and +∞ at the ends).

Search with powers of 2​

Instead of an interval, keep pointer i and exponent k. Test i + 2ᵏ; advance if the predicate is still 0, then decrease k. Common on trees (LCA, k-th ancestor) and Fenwick “find k-th nonzero.”

Check: predicates & variants​

Quiz

Binary search variants

1 / 4

Predicate binary search requires f to be…

Pick an answer to see if you are right.

Practice drills​

Sandbox versions of classic interview binary-search problems. Starters fail until the logic is right.

Activity: Search insert position

Sorted unique nums. Return the index of target, or where it would be inserted to keep order (lower bound).

Input: n target then n ints.

Contest / interview problems​

Solve on LeetCode (same ideas as the drills).

Find First and Last Position of Element in Sorted Array​

Judge: LeetCode 34

Given a sorted array (duplicates allowed), return [first, last] indices of target, or [-1, -1].

Why this lesson?

Lower bound + upper bound (or two binary searches). Exactly the half-open equal range.

Cheat sheet​

SituationWhat to binary-search
Sorted array membershipIndex interval with a[l] ≤ k < a[r]
First ≥ / first >Lower / upper bound
Expensive monotone yes/noPredicate f
Optimize a numeric answerFeasibility check on λ
Continuous f(x)=yHalve real interval to ±δ
Trees / FenwickPowers of two from a pointer

Previous: Basic Geometry · 0-1 BFS

Source: CP-Algorithms — Binary Search