Binary search

coreCommon atGoogleMetaAmazonAnthropictrading firmsRead firstArraysComplexity analysisPractise in the Sandbox →

Binary search finds the boundary in a range where a yes/no question flips from false to true, by testing the middle and discarding the half that can’t hold the boundary. Keep an invariant (“left of lo is false, from hi on is true”) and the loop writes itself. O(log n) tests, and the range can be array indices or possible answers.

The idea in plain words

Guess a number from 1 to 1,000 with “higher / lower” hints. Guessing 500 first throws away half the possibilities, whatever the answer. Ten guesses always suffice, because 2¹⁰ = 1,024.

The real idea is more general than “find a value in a sorted array”. You need a question with one switch point:

x:      0  1  2  3  4  5  6  7  8
ok(x):  F  F  F  F  T  T  T  T  T
                    ^ the boundary

That shape is called monotone: once the answer is true, it stays true. Any monotone question can be binary searched:

• “Is xs[i] >= target?” on a sorted array. The boundary is the lower bound.
• “Is x * x >= n?” over numbers. The boundary is the square root.
• “Is a budget of b enough?” over budgets. The boundary is the smallest budget that works.

The last two search over answers, not array slots. That’s “binary search on the answer”, and it’s the version interviews like most.

See it

Search a sorted array. Try a target that’s present several times, one that’s absent, and one bigger than everything. Switch between lower and upper bound and watch what changes: only the comparison.

Lower and upper bound on a sorted array

step through

sorted values (up to 14)target

lo

2

4

4

4

7

9

12

15

15

20

·

012345678910

hi

lo0

hi10

probes0

still possibleprobeknown: fails the ruleknown: passes the ruleanswer

Find the first index with xs[i] ≥ 4. Invariant: everything left of lo fails the rule, everything at or right of hi passes. The answer is in [lo, hi], and hi = 10 (past the end) is a legal answer.

↺◀▶ Play▶1 / 10

Now the same loop over a range of numbers. The yes/no line at the bottom is the predicate. The curve above it is the function being tested; the boundary is where it crosses the threshold. Keep the truth hidden: binary search never needs to see it.

Binary search on a monotone predicate

step through

n (≤ 100,000)

Question: smallest x whose square reaches n (a ceiling square root).

lo0

hi37

tests0

known falseknown true[lo, hi): still unknowntest at mid

The predicate "x² ≥ n" is false for small x and true for large x, with one switch point. We never look at the whole line: the invariant is "left of lo is false, hi and beyond is true". (The search range [0, 36] is any range certain to contain the switch.)

↺◀▶ Play▶1 / 7

When to reach for it

The problem says…	Why binary search fits
sorted input, “find / count / insert position of”	Sorted order makes xs[i] >= target monotone.
“minimum X such that …” or “maximum X such that …”	If X works, every bigger (or smaller) X works too: search the answer.
answer is a number in a huge range (up to 10⁹, 10¹⁸)	log₂(10¹⁸) ≈ 60 tests. Trying every value is impossible.
“it’s easy to check a candidate, hard to construct the best”	Wrap the checker as the predicate; binary search does the optimizing.
a time limit that hints O(n log n) or O(log n) per query	One sort plus binary searches is the classic O(n log n) shape.
a stream of queries against a fixed sorted list	Each query is O(log n); see sorted containers.

How it works

Lower and upper bound

Learn one template and reuse it. This one uses a half-open range [lo, hi), where hi = n means “past the end”, so “not found” needs no special case.

1. Set lo = 0, hi = n. Invariant: every index < lo fails the rule, every index >= hi passes it.
2. While lo < hi, more than one candidate remains. Probe mid = lo + (hi - lo) / 2.
3. If mid fails the rule, it and everything left of it fail: lo = mid + 1.
4. Otherwise mid passes and might be the answer: hi = mid (keep it). When the loop ends, lo == hi is the first passing index.

Python

bounds.py

from bisect import bisect_left, bisect_right


def lower_bound(xs: list[int], target: int) -> int:
    """First index i with xs[i] >= target (len(xs) if none). xs must be sorted."""
    lo, hi = 0, len(xs)              # 1. answer lives in [lo, hi]; hi = len means "past the end"
    while lo < hi:                   # 2. stop when the range has shrunk to one candidate
        mid = (lo + hi) // 2
        if xs[mid] < target:
            lo = mid + 1             # 3. mid is too small, and so is everything left of it
        else:
            hi = mid                 # 4. mid might be the answer: keep it in range
    return lo


def upper_bound(xs: list[int], target: int) -> int:
    """First index i with xs[i] > target. Only the comparison differs."""
    lo, hi = 0, len(xs)
    while lo < hi:
        mid = (lo + hi) // 2
        if xs[mid] <= target:        # <= instead of <: equal values are skipped too
            lo = mid + 1
        else:
            hi = mid
    return lo


if __name__ == "__main__":
    xs = [1, 3, 3, 3, 7, 9]
    assert lower_bound(xs, 3) == 1 and upper_bound(xs, 3) == 4
    assert lower_bound(xs, 4) == 4 == upper_bound(xs, 4)   # absent: both give the insert point
    assert lower_bound(xs, 0) == 0 and lower_bound(xs, 10) == 6
    assert lower_bound([], 5) == 0
    for t in range(-1, 12):                                 # agree with the stdlib
        assert lower_bound(xs, t) == bisect_left(xs, t)
        assert upper_bound(xs, t) == bisect_right(xs, t)
    print("ok")

TypeScript

bounds.ts

import assert from "node:assert/strict";

/** First index i with xs[i] >= target (xs.length if none). xs must be sorted. */
export function lowerBound(xs: number[], target: number): number {
  let lo = 0;
  let hi = xs.length; // 1. answer lives in [lo, hi]; hi = length means "past the end"
  while (lo < hi) { // 2. stop when the range has shrunk to one candidate
    const mid = lo + ((hi - lo) >> 1);
    if (xs[mid] < target) lo = mid + 1; // 3. mid is too small, and so is everything left of it
    else hi = mid; // 4. mid might be the answer: keep it in range
  }
  return lo;
}

/** First index i with xs[i] > target. Only the comparison differs. */
export function upperBound(xs: number[], target: number): number {
  let lo = 0;
  let hi = xs.length;
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (xs[mid] <= target) lo = mid + 1; // <= instead of <: equal values are skipped too
    else hi = mid;
  }
  return lo;
}

const xs = [1, 3, 3, 3, 7, 9];
assert.equal(lowerBound(xs, 3), 1);
assert.equal(upperBound(xs, 3), 4);
assert.equal(lowerBound(xs, 4), 4); // absent: both give the insert point
assert.equal(upperBound(xs, 4), 4);
assert.equal(lowerBound(xs, 0), 0);
assert.equal(lowerBound(xs, 10), 6);
assert.equal(lowerBound([], 5), 0);
console.log("ok");

C#

bounds.cs

// First index i with xs[i] >= target (xs.Length if none). xs must be sorted.
static int LowerBound(int[] xs, int target)
{
    int lo = 0, hi = xs.Length;          // 1. answer lives in [lo, hi]; hi = Length means "past the end"
    while (lo < hi)                      // 2. stop when the range has shrunk to one candidate
    {
        int mid = lo + (hi - lo) / 2;    // no (lo + hi) overflow near int.MaxValue
        if (xs[mid] < target) lo = mid + 1; // 3. mid is too small, and so is everything left of it
        else hi = mid;                   // 4. mid might be the answer: keep it in range
    }
    return lo;
}

// First index i with xs[i] > target. Only the comparison differs.
static int UpperBound(int[] xs, int target)
{
    int lo = 0, hi = xs.Length;
    while (lo < hi)
    {
        int mid = lo + (hi - lo) / 2;
        if (xs[mid] <= target) lo = mid + 1; // <= instead of <: equal values are skipped too
        else hi = mid;
    }
    return lo;
}

int[] xs = [1, 3, 3, 3, 7, 9];
if (LowerBound(xs, 3) != 1 || UpperBound(xs, 3) != 4) throw new Exception("bounds of 3");
if (LowerBound(xs, 4) != 4 || UpperBound(xs, 4) != 4) throw new Exception("absent value");
if (LowerBound(xs, 10) != 6 || LowerBound([], 5) != 0) throw new Exception("edges");
// Array.BinarySearch returns ~insertPoint when absent (and ANY matching index when present).
if (~Array.BinarySearch(xs, 4) != LowerBound(xs, 4)) throw new Exception("complement");
Console.WriteLine("ok");

	lower bound	upper bound
returns	first index with xs[i] >= target	first index with xs[i] > target
go right when	xs[mid] < target	xs[mid] <= target
Python	bisect.bisect_left(xs, t)	bisect.bisect_right(xs, t)
C#	Array.BinarySearch / List<T>.BinarySearch: index of some match, or ~insertionPoint (a negative number) when absent. Not guaranteed to be the first match.	write it yourself
TS / JS	none built in: write it yourself	none built in

C#'s BinarySearch with duplicates

Array.BinarySearch returns the index of a matching element when there are several, not necessarily the first. If you need the first or last, use your own lower/upper bound. When the value is absent, apply ~ to the negative result to get the insertion point.

Binary search on the answer

1. Write the predicate ok(x) and convince yourself it is monotone. Say which way it flips.
2. Pick lo and hi so the answer is certainly inside. Here: ok(lo) is known true, and nothing past hi matters.
3. Probe mid. For “last true”, round up: mid = lo + (hi - lo + 1) / 2. If ok(mid), the answer is mid or to its right: lo = mid. If not, hi = mid - 1.

Python

isqrt.py

from collections.abc import Callable
import math


def last_true(lo: int, hi: int, ok: Callable[[int], bool]) -> int:
    """Largest x in [lo, hi] with ok(x) True, given ok is True...True False...False
    and ok(lo) is True. The invariant: ok(lo) is always True, ok(hi + 1) always False."""
    while lo < hi:
        mid = lo + (hi - lo + 1) // 2   # 1. round UP, or lo = mid could loop forever
        if ok(mid):
            lo = mid                    # 2. mid works: the answer is mid or to its right
        else:
            hi = mid - 1                # 3. mid fails: so does everything to its right
    return lo


def isqrt(n: int) -> int:
    """floor(sqrt(n)) without floating point: the largest x with x * x <= n."""
    if n < 0:
        raise ValueError("n must be >= 0")
    return last_true(0, n, lambda x: x * x <= n)  # search the ANSWER space, not an array


if __name__ == "__main__":
    assert [isqrt(n) for n in range(10)] == [0, 1, 1, 1, 2, 2, 2, 2, 2, 3]
    assert isqrt(10**18) == 10**9
    for n in [0, 1, 15, 16, 17, 99_999, 2**40 + 7]:
        assert isqrt(n) == math.isqrt(n)        # the stdlib has it since 3.8
    print("ok")

TypeScript

isqrt.ts

import assert from "node:assert/strict";

/** Largest x in [lo, hi] with ok(x) true, given ok is true...true false...false
 *  and ok(lo) is true. Invariant: ok(lo) is always true, ok(hi + 1) always false. */
export function lastTrue(lo: bigint, hi: bigint, ok: (x: bigint) => boolean): bigint {
  while (lo < hi) {
    const mid = lo + (hi - lo + 1n) / 2n; // 1. round UP, or lo = mid could loop forever
    if (ok(mid)) lo = mid; // 2. mid works: the answer is mid or to its right
    else hi = mid - 1n; // 3. mid fails: so does everything to its right
  }
  return lo;
}

/** floor(sqrt(n)) without floating point: the largest x with x * x <= n.
 *  bigint, because x * x overflows 2^53 long before n does. */
export function isqrt(n: bigint): bigint {
  if (n < 0n) throw new RangeError("n must be >= 0");
  return lastTrue(0n, n, (x) => x * x <= n); // search the ANSWER space, not an array
}

assert.deepEqual([0n, 1n, 2n, 3n, 4n, 8n, 9n].map(isqrt), [0n, 1n, 1n, 1n, 2n, 2n, 3n]);
assert.equal(isqrt(10n ** 18n), 10n ** 9n);
assert.equal(isqrt(10n ** 18n - 1n), 10n ** 9n - 1n);
console.log("ok");

C#

isqrt.cs

// Largest x in [lo, hi] with ok(x) true, given ok is true...true false...false
// and ok(lo) is true. Invariant: ok(lo) is always true, ok(hi + 1) always false.
static long LastTrue(long lo, long hi, Func<long, bool> ok)
{
    while (lo < hi)
    {
        long mid = hi - (hi - lo) / 2;       // 1. round UP, or lo = mid could loop forever
                                             //    (lo + (hi - lo + 1) / 2 overflows at long.MaxValue)
        if (ok(mid)) lo = mid;               // 2. mid works: the answer is mid or to its right
        else hi = mid - 1;                   // 3. mid fails: so does everything to its right
    }
    return lo;
}

// floor(sqrt(n)) without floating point: the largest x with x * x <= n.
static long ISqrt(long n)
{
    if (n < 0) throw new ArgumentOutOfRangeException(nameof(n));
    // x <= n / x is x * x <= n without overflowing long for big x.
    return LastTrue(0, n, x => x == 0 || x <= n / x);
}

long[] got = [ISqrt(0), ISqrt(1), ISqrt(3), ISqrt(4), ISqrt(8), ISqrt(9)];
if (!got.SequenceEqual([0L, 1, 1, 2, 2, 3])) throw new Exception(string.Join(",", got));
if (ISqrt(1_000_000_000_000_000_000) != 1_000_000_000) throw new Exception("10^18");
if (ISqrt(long.MaxValue) != 3_037_000_499) throw new Exception("max");
Console.WriteLine("ok");

Why round up for 'last true'?

With lo = 3, hi = 4, rounding down gives mid = 3. If ok(3) is true, lo = mid sets lo to 3 again: an infinite loop. Rounding up gives mid = 4, so either branch shrinks the range. Rule of thumb: if a branch sets lo = mid, round up; if it sets hi = mid, round down.

What it costs

	Time	Extra space
Linear scan	O(n)	O(1)
Binary search on an array	O(log n) comparisons	O(1) iterative, O(log n) recursive
Binary search on an answer in [lo, hi]	O(log(hi − lo) · C), where C is the cost of one ok(x) call	whatever ok needs
Sort once, then q searches	O(n log n + q log n)	O(n) or O(1)

Each probe halves the remaining candidates, so after k probes there are n / 2ᵏ left. That reaches 1 when k = log₂ n. For n = 10⁹ that’s about 30 probes. Drag n and compare the curves:

How fast does work grow?

drag n

O(1)O(log n)O(n)O(n log n)O(n²)O(2ⁿ)

n = 16

O(log n): 4 opsO(n): 16 ops

On the answer, the checker usually dominates: an O(n) ok over a range up to 10⁹ costs about 30·n. Say that product out loud.

Variations you’ll meet

• First true / last true. Every binary search is one of these two. Lower bound is “first true” of xs[i] >= t. “Largest x with x² ≤ n” is “last true”.
• Minimize the maximum / maximize the minimum. These phrasings almost always mean binary search on the answer plus a feasibility check, and the check is often a simple greedy pass.
• Real-valued answers. For floating point, loop a fixed number of times (say 100) instead of while lo < hi, or until hi − lo < ε. Each iteration halves the error.
• Arrays that are only “partly sorted”. The values aren’t monotone, but you may still find some yes/no question about an index that is. If you can, the same loop applies.
• Exponential (galloping) search. Unknown or unbounded size: probe 1, 2, 4, 8… until you overshoot, then binary search the last gap. O(log answer).
• Binary search inside a data structure. Sorted containers and BSTs run the same halving logic on a tree, so inserts stay cheap.

Pitfalls

• Overflow in (lo + hi) / 2. In C# and Java, with int indices near 2³¹, the sum overflows. Use lo + (hi - lo) / 2. The C# snippet above shows a sneakier version: hi - lo + 1 overflows when hi is long.MaxValue. Writing hi - (hi - lo) / 2 rounds up without the + 1.
• Infinite loops. A branch that doesn’t shrink the range (lo = mid with rounding down). Check the two-element case by hand.
• Mixing conventions. Closed [lo, hi] with while lo <= hi and hi = mid - 1, or half-open [lo, hi) with while lo < hi and hi = mid. Both work. Mixing them doesn’t. Pick one and keep it.
• A predicate that isn’t monotone. Then binary search returns a switch point, not the answer. Prove monotonicity first (“if c works, c + 1 also works because…”).
• Wrong initial bounds. hi must be a value where the answer is guaranteed (often the sum, the max, or n). lo must not skip a valid answer (often 0 or 1).
• Overflow inside the predicate. mid * mid overflows 64 bits once mid passes about 3·10⁹. Compare mid <= n / mid, or use bigint in TS.
• TS number is a double. Math.floor the midpoint. (lo + hi) >> 1 is only safe below 2³¹.

In the interview

• Ask: is the input sorted? Can there be duplicates? What should “not found” return: −1, the insertion point, or an error?
• For an optimization question, say: “The check is easy and monotone: if X works, anything bigger works. So I’ll binary search X between lo and hi.” That sentence earns a lot of credit.
• State the invariant before you write the loop: “Everything left of lo is false, everything from hi on is true.” Then each branch is just “keep the invariant”.
• Trace the two-element case aloud to show the loop terminates.
• Likely follow-ups: “Now there are duplicates”, “Return the insertion point”, “What’s the complexity of the checker times the search?”, “What if the range is real numbers?”

Check yourself

Check yourself

pick one

In the half-open lower-bound template (while lo < hi), xs[mid] >= target. Why is the update hi = mid and not hi = mid − 1?

ATo avoid an infinite loopBBecause mid itself might be the first index that passes, so it must stay a candidateCBecause hi is exclusive, so mid − 1 would skip two elementsDIt makes no difference

Check yourself

pick one

You search for the smallest integer x in [1, 10^9] with ok(x) true, and ok is monotone. One call to ok costs O(n) with n = 10^5. Roughly how many operations in total?

A10^9 · 10^5B30 · 10^5 = 3·10^6C10^5 · log(10^5) ≈ 1.7·10^6D30

Check yourself

pick one

A 'last true' search uses lo = mid when ok(mid) is true and hi = mid − 1 otherwise. With lo = 6 and hi = 7, which midpoint formula avoids an infinite loop?

Amid = (lo + hi) / 2, rounded downBmid = lo + (hi − lo + 1) / 2, rounded upCEither oneDNeither: this template always loops

Practice on your own

These are classic textbook exercises, not gym questions:

• Guess the number: find a hidden integer in [1, n] given only “higher / lower / correct” answers.
• First bad version: versions 1..n, all versions after the first bad one are bad. Find it with as few checks as possible.
• Place k items on positions on a line to make the minimum gap between them as large as possible (“aggressive cows”).
• k-th smallest value in a matrix whose rows and columns are sorted (search on the value, count how many are ≤ it).
• Cube root of a real number to 6 decimal places, using a fixed number of iterations.

Go deeper

• cp-algorithms: Binary search: the invariant-based “lo is always false, hi is always true” formulation and search on real numbers.
• Python docs: bisect and .NET Array.BinarySearch: exact return values, including the ~index convention.
• Joshua Bloch, “Nearly All Binary Searches and Mergesorts are Broken” (Google Research blog, 2006): the (lo + hi) / 2 overflow bug that sat in the JDK for nine years.
• Jon Bentley, Programming Pearls, column 4: writing binary search correctly with loop invariants.

Related

SortingSort first, then binary search: the O(n log n) staple.

Sorted containersbisect, SortedSet and friends for dynamic sorted data.

Greedy algorithmsThe usual checker inside binary search on the answer.

Divide and conquerBinary search is its smallest case: T(n) = T(n/2) + O(1).