Binary search that is correct the first time

Binary search finds a position in sorted data by halving the part that is still in doubt. Each comparison rules out half of what is left, so 18 comparisons settle the 200,000 values of a typical coding-round input and 30 settle a billion. The idea fits in one sentence; the details are where solutions fail: < or <=, mid or mid + 1, hi = n or hi = n - 1, and a midpoint that overflows. Getting it right the first time means deriving each of those choices from one stated invariant, and checking that the loop ends, instead of recalling a template under pressure. This lesson builds that template, the lower bound on a half-open range, and solves a first problem with it in four languages. Then it catches three one-token slips on every small input, measures an overflowing midpoint in Java and C++, and maps the template onto each language’s library.

When a coding round wants binary search

Binary search applies when the data is sorted, or can be sorted once, and the question asks for a boundary in it. The wording usually gives it away:

• Sorted data and many questions (“the scores are sorted”, “answer q queries”): search once per query, for a lower or an upper bound.
• A boundary or a count (“the first position where”, “the last value at most”, “how many are at least”): one bound, or the difference of two bounds.
• A yes-or-no condition that flips once (“the smallest capacity that ships every parcel within D days”): search the range of possible answers for the first one that works.

The limits confirm it. Scanning 10⁵ sorted values for each of 10⁵ queries costs about 10¹⁰ steps, far beyond the planning figures of 10⁷ to 10⁸ simple steps a second from the lesson on reading constraints; one binary search per query costs about 1.7 × 10⁶. An answer that can be as large as 10⁹ cannot be tried value by value either, but when checking one candidate is cheap and the condition flips only once, 30 checks find it.

Binary search is the wrong tool in three cases. Data that is unsorted and searched only once is faster to scan, because sorting it costs O(n log n), more than the O(n) scan it would replace. A linked list has no quick way to reach its middle, so every probe costs a walk along the list. And a condition that can turn back from true to false breaks the method: the search still returns a position, without any error, and the position means nothing.

The rest of this module puts the same template to work: first and last positions and counts, conditions that flip once, searching on the answer for capacities and speeds, minimising the largest part and maximising the smallest gap, rotated arrays and peaks, sorted matrices, and the partition search behind the median of two sorted arrays.

One template: the lower bound

For a sorted list a and a value x, the lower bound is the first position whose value is at least x, or len(a) when there is none. It is also the number of values below x. Most searches in this module are a lower bound in disguise, so this is the loop to know well.

The lesson on dry runs derived this loop’s boundaries from that sentence: lo = 0 and hi = len(a), while lo < hi, lo = mid + 1 when a[mid] < x, and hi = mid otherwise. Two arguments make it correct, and both are short enough to say aloud in an interview.

Each pass keeps the invariant. While lo < hi, the midpoint (lo + hi) // 2 lies in [lo, hi). If a[mid] < x, the sorted order puts every value up to a[mid] below x as well, so moving lo past mid keeps the left part true. Otherwise a[mid] and everything after it are x or more, so moving hi down to mid keeps the right part true, and a[mid], which may be the answer, becomes the first value of that part.

The loop ends after at most ⌊log₂ n⌋ + 1 passes. Call L = hi - lo the length of the unknown part. Setting hi = mid leaves half of L, rounded down; setting lo = mid + 1 leaves half of L rounded up, minus one, which is never more. So every pass at least halves L, rounding down, and L reaches 0 after at most ⌊log₂ n⌋ + 1 passes: 18 for 200,000 values, 30 for a billion. Then lo == hi, nothing is unknown, and the invariant says what lo is: the first position whose value is not below x.

You have met this loop before if you have used Python’s bisect_left: the pure Python version in CPython’s Lib/bisect.py is these same lines, which the module then replaces with a faster C implementation. Go’s sort.Search is the same template too, and its source states the invariant in a comment, written for a yes-or-no function f: f(i - 1) is false and f(j) is true.

A problem solved in full: cut-off counts

Two examples, which become the first tests:

• The scores [35, 42, 42, 58, 61, 61, 61, 77, 90] with the cut-offs [61, 62, 0, 91] give [5, 2, 9, 0]. A score equal to the cut-off counts, so the three 61s all count for the cut-off 61; nobody reaches 91, and a cut-off of 0 counts everyone.
• No scores at all, with the cut-off 50, give [0].

The brute force

For each cut-off, count the scores that reach it: one scan of n scores per cut-off, so O(n × q) comparisons, which is 4 × 10¹⁰ at the limits. That is hundreds of times more than a time limit of a second or two allows. Keep it anyway: it is too slow to submit and too simple to get wrong, which makes it the right judge for the fast version.

What to notice

Because the scores are sorted, the scores that reach a cut-off c form one block at the end of the list. The block’s length is n minus the position where it starts, and that position is the lower bound of c. Put differently, the test “is this score at least c?” is false for a prefix of the list and true for the rest, which is exactly the shape binary search needs.

The fast version

For each cut-off c, the answer is n - lower_bound(scores, c). Each lower bound takes at most 18 passes over 200,000 scores, so 200,000 cut-offs cost at most 3.6 million passes. Sorting the cut-offs and walking both lists together would also work, in O(n + q log q), but then the answers have to be put back in the order the cut-offs were asked.

A dry run

The search for the cut-off 61 on the nine example scores:

• Pass 1: lo = 0, hi = 9, mid = 4. scores[4] is 61, not below 61, so hi = 4.
• Pass 2: lo = 0, hi = 4, mid = 2. scores[2] is 42, below 61, so lo = 3.
• Pass 3: lo = 3, hi = 4, mid = 3. scores[3] is 58, below 61, so lo = 4.
• End: lo == hi, both 4, so 9 − 4 = 5 candidates reach the cut-off.

Three passes, within the bound of four for nine values. The first pass is the one to notice: scores[4] equals the cut-off, and the search does not stop there. A 61 further left would also be the first score of at least 61, so hi moves down to 4 and the search keeps looking; passes 2 and 3 show that scores[3] is still below the cut-off.

The code in four languages

Python and JavaScript run here in your browser; the Java and C++ versions are built and run after them, with the commands you would type in a terminal.

"""Cut-off counts: for each cut-off, how many sorted scores are at least the cut-off."""


def lower_bound(a, x):
    """The first position i with a[i] >= x, or len(a) when there is none."""
    lo, hi = 0, len(a)
    # Invariant: all of a[:lo] is below x, all of a[hi:] is x or more, a[lo:hi] is still unknown.
    while lo < hi:
        mid = (lo + hi) // 2  # lo <= mid < hi
        if a[mid] < x:
            lo = mid + 1  # a[mid], and everything left of it, is below x
        else:
            hi = mid  # a[mid] is x or more, so it may be the answer
    return lo  # lo == hi: nothing is unknown, and lo values are below x


def at_least(scores, cutoffs):
    n = len(scores)
    return [n - lower_bound(scores, c) for c in cutoffs]


scores = [35, 42, 42, 58, 61, 61, 61, 77, 90]
print(at_least(scores, [61, 62, 0, 91]))
print(at_least([], [50]))

[5, 2, 9, 0]
[0]

// Cut-off counts: for each cut-off, how many sorted scores are at least the cut-off.

// The first position i with a[i] >= x, or a.length when there is none.
function lowerBound(a, x) {
  let lo = 0;
  let hi = a.length;
  // Invariant: all of a[0..lo) is below x, all of a[hi..) is x or more, a[lo..hi) is still unknown.
  while (lo < hi) {
    const mid = lo + ((hi - lo) >>> 1); // lo <= mid < hi
    if (a[mid] < x) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

function atLeast(scores, cutoffs) {
  return cutoffs.map((c) => scores.length - lowerBound(scores, c));
}

const show = (list) => `[${list.join(', ')}]`;
const scores = [35, 42, 42, 58, 61, 61, 61, 77, 90];
console.log(show(atLeast(scores, [61, 62, 0, 91])));
console.log(show(atLeast([], [50])));

[5, 2, 9, 0]
[0]

import java.util.Arrays;

// Cut-off counts: for each cut-off, how many sorted scores are at least the cut-off.
public class Cutoff {
    // The first position i with a[i] >= x, or a.length when there is none.
    static int lowerBound(int[] a, int x) {
        int lo = 0, hi = a.length;
        // Invariant: all of a[0..lo) is below x, all of a[hi..) is x or more, a[lo..hi) is still unknown.
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2; // lo <= mid < hi, and the sum lo + hi is never formed
            if (a[mid] < x) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }

    static int[] atLeast(int[] scores, int[] cutoffs) {
        int[] counts = new int[cutoffs.length];
        for (int i = 0; i < cutoffs.length; i++) counts[i] = scores.length - lowerBound(scores, cutoffs[i]);
        return counts;
    }

    public static void main(String[] args) {
        int[] scores = {35, 42, 42, 58, 61, 61, 61, 77, 90};
        System.out.println(Arrays.toString(atLeast(scores, new int[] {61, 62, 0, 91})));
        System.out.println(Arrays.toString(atLeast(new int[0], new int[] {50})));
    }
}

// Cut-off counts: for each cut-off, how many sorted scores are at least the cut-off.
#include <cstddef>
#include <print>
#include <vector>

// The first position i with a[i] >= x, or a.size() when there is none.
std::size_t lower_bound_index(const std::vector<int>& a, int x) {
    std::size_t lo = 0, hi = a.size();
    // Invariant: all of a[0, lo) is below x, all of a[hi, n) is x or more, a[lo, hi) is still unknown.
    while (lo < hi) {
        std::size_t mid = lo + (hi - lo) / 2;  // lo <= mid < hi
        if (a[mid] < x) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

std::vector<std::size_t> at_least(const std::vector<int>& scores, const std::vector<int>& cutoffs) {
    std::vector<std::size_t> counts;
    for (int c : cutoffs) counts.push_back(scores.size() - lower_bound_index(scores, c));
    return counts;
}

void show(const std::vector<std::size_t>& list) {
    std::print("[");
    for (std::size_t i = 0; i < list.size(); ++i) std::print("{}{}", i ? ", " : "", list[i]);
    std::println("]");
}

int main() {
    const std::vector<int> scores{35, 42, 42, 58, 61, 61, 61, 77, 90};
    show(at_least(scores, {61, 62, 0, 91}));
    show(at_least({}, {50}));
}

from session import run, versions

# Cutoff.java runs as a single source file; cutoff.cpp is built with warnings and both sanitizers on.
versions("java -version", "clang++ --version")
run("""
java Cutoff.java
clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined cutoff.cpp -o cutoff && ./cutoff
""")

# openjdk version "27"
# Apple clang version 21.0.0 (clang-2100.3.34.2)
$ java Cutoff.java
[5, 2, 9, 0]
[0]
$ clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined cutoff.cpp -o cutoff && ./cutoff
[5, 2, 9, 0]
[0]

All four print the same two lines. Java and C++ compute the midpoint as lo + (hi - lo) / 2, and JavaScript as lo + ((hi - lo) >>> 1); the section on midpoints below shows what the plain sum does wrong. The C++ version keeps positions in std::size_t, an unsigned type. That is safe because this template never computes mid - 1: in a search that does, mid - 1 with mid equal to 0 wraps around to the largest std::size_t. In Go the loop reads the same, and sort.Search with the condition scores[i] >= c returns the same position.

Check it against a judge, and count the passes

"""The lower bound checked two ways: its answers against bisect_left, and its passes against floor(log2 n) + 1."""

import random
from bisect import bisect_left


def lower_bound(a, x):
    """The first position i with a[i] >= x, or len(a); also returns how many passes the loop made."""
    lo, hi, passes = 0, len(a), 0
    while lo < hi:
        passes += 1
        mid = (lo + hi) // 2
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo, passes


# 1. Answers: 10,000 random sorted lists, short and full of repeats, so ties and the edges come up often.
rng = random.Random(7)
mismatches = 0
for _ in range(10_000):
    a = sorted(rng.randint(0, 5) for _ in range(rng.randint(0, 12)))
    x = rng.randint(-1, 6)
    if lower_bound(a, x)[0] != bisect_left(a, x):
        mismatches += 1
print(f"10,000 random lists: {mismatches} answers differ from bisect_left")

# 2. Passes: every x for small n; for large n the two ends and 1,000 random values. A range object is a sorted
# sequence that supports len() and indexing without storing its values, so n can reach a billion.
print(f"{'n':>13}  {'most passes':>11}  {'floor(log2 n) + 1':>17}")
for n in [1, 2, 3, 4, 5, 7, 8, 9, 1_000, 1_000_000, 1_000_000_000]:
    a = range(0, 2 * n, 2)  # 0, 2, 4, ...: the even numbers below 2n
    xs = range(-1, 2 * n + 1) if n <= 1_000 else [-1, 2 * n] + [rng.randrange(-1, 2 * n + 1) for _ in range(1_000)]
    most = max(lower_bound(a, x)[1] for x in xs)
    print(f"{n:>13,}  {most:>11}  {n.bit_length():>17}")

10,000 random lists: 0 answers differ from bisect_left
            n  most passes  floor(log2 n) + 1
            1            1                  1
            2            2                  2
            3            2                  2
            4            3                  3
            5            3                  3
            7            3                  3
            8            4                  4
            9            4                  4
        1,000           10                 10
    1,000,000           20                 20
1,000,000,000           30                 30

The random lists are short and hold only the values 0 to 5, so repeated values, an x below everything and an x above everything come up thousands of times, and no answer differs from bisect_left. The table measures the pass bound: for every n, the most passes the loop made equals ⌊log₂ n⌋ + 1, which Python computes as n.bit_length(). The search over a billion values runs on a range object, a sorted sequence that Python can index without storing it: the template needs nothing from its input but a length and indexing.

Three slips that look right

Each slip below changes one token of the template, and each looks as reasonable as the original. The test tries every sorted list of up to five values from 0 to 3 against bisect_left, shortest first, so the first failure it reports is also the smallest:

"""Three one-token slips in the lower-bound loop, each tried on every small sorted list against bisect_left."""

from bisect import bisect_left
from itertools import combinations_with_replacement

STEP_LIMIT = 100  # a search of at most five values needs 3 passes; 100 means the loop is stuck


class Stuck(Exception):
    pass


def template(a, x):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo


def keeps_mid(a, x):  # lo = mid instead of lo = mid + 1
    lo, hi, passes = 0, len(a), 0
    while lo < hi:
        passes += 1
        if passes > STEP_LIMIT:
            raise Stuck(f"lo = {lo}, hi = {hi} and mid = {(lo + hi) // 2} on every pass")
        mid = (lo + hi) // 2
        if a[mid] < x:
            lo = mid
        else:
            hi = mid
    return lo


def drops_mid(a, x):  # hi = mid - 1 instead of hi = mid
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid - 1
    return lo


def closed_loop(a, x):  # while lo <= hi, with hi still len(a)
    lo, hi = 0, len(a)
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid - 1
    return lo


def cases():
    """Every sorted list of 0 to 5 values from 0 to 3, shortest first, with every x from -1 to 4."""
    for n in range(6):
        for values in combinations_with_replacement(range(4), n):
            for x in range(-1, 5):
                yield list(values), x


def first_failure(search):
    for a, x in cases():
        want = bisect_left(a, x)
        try:
            got = search(a, x)
        except Stuck as e:
            return f"never ends on a = {a}, x = {x}: {e}"
        except IndexError:
            return f"reads past the end of a = {a} for x = {x} (IndexError)"
        if got != want:
            return f"returns {got} instead of {want} on a = {a}, x = {x}"
    return "no failure"


print(f"{sum(1 for _ in cases())} cases: every sorted list of up to 5 values from 0 to 3, every x from -1 to 4")
for name, search in [("the template", template), ("lo = mid", keeps_mid), ("hi = mid - 1", drops_mid), ("while lo <= hi", closed_loop)]:
    print(f"{name:<15} {first_failure(search)}")

756 cases: every sorted list of up to 5 values from 0 to 3, every x from -1 to 4
the template    no failure
lo = mid        never ends on a = [0], x = 1: lo = 0, hi = 1 and mid = 0 on every pass
hi = mid - 1    returns 0 instead of 1 on a = [0, 1], x = 1
while lo <= hi  reads past the end of a = [] for x = -1 (IndexError)

• lo = mid makes no progress when hi is lo + 1: then mid equals lo, and a value below x leaves lo where it was. The same pass repeats for ever, which the step limit turns into a report; the list [0] is enough. Every branch has to shrink the unknown part, and here only mid + 1 does.
• hi = mid - 1 throws away a[mid], which may be the answer. On [0, 1] with x = 1 the first probe lands on the 1, the search moves past it, and it returns 0.
• while lo <= hi belongs to the closed-range search, which starts with hi = len(a) - 1. Mixed with the half-open start hi = len(a), it reads one position past the end, and the empty list shows it at once.

All three can pass the samples of a problem, because samples rarely include a list of one value or an empty list. All three fail within the 756 small cases, which take a fraction of a second, so an exhaustive check of small inputs is the cheapest test a binary search can have.

The closed-range search is a template of its own, not a slip, and Java’s Arrays.binarySearch is built on it. The difference matters as soon as a value repeats:

Upper bound, first, last and count

The upper bound is the first position whose value is greater than x. Its invariant moves the values equal to x into the left part: a[:lo] holds values that are at most x, and a[hi:] values greater than x. The loop is the template with one comparison changed, and the exercise at the end of this lesson asks you to work out which one. With both bounds, the usual questions about a sorted list take one line each:

The checks matter because a bound can be n, one past the last position, and a bound minus one can be −1. Python does not complain about the second: a[-1] quietly reads the last value instead of failing.

Predict what this prints before you look at its output:

from bisect import bisect_left, bisect_right

a = [3, 5, 5, 5, 9]
print(bisect_left(a, 5), bisect_right(a, 5), bisect_left(a, 7))

1 4 4

The midpoint, and when lo + hi overflows

Python’s integers have no fixed size, so (lo + hi) // 2 is always exact. In Java and C++ the sum of two 32-bit ints can pass 2,147,483,647 before it is halved. With an array that takes more than a billion elements, which coding rounds do not use, but the same loop often searches a range of answers, such as every whole number up to 2,000,000,000, and there the sum overflows on ordinary inputs. Here is such a search, for the smallest k with k² ≥ 3 × 10¹⁸, with three midpoints in each language:

// The smallest whole number k with k * k >= n, searched for between 0 and 2,000,000,000 with three midpoints.
public class SquareRoot {
    interface Midpoint {
        int of(int lo, int hi);
    }

    static void search(String name, Midpoint midpoint, long n) {
        int lo = 0, hi = 2_000_000_000;
        int probes = 0;
        boolean warned = false;
        // Invariant: every k below lo has k * k < n, every k from hi on has k * k >= n.
        while (lo < hi) {
            if (++probes > 64) { // 31 probes settle 2,000,000,000 values, so 64 means something is wrong
                System.out.println(name + " still searching after 64 probes: lo = " + lo + ", hi = " + hi);
                return;
            }
            int mid = midpoint.of(lo, hi);
            if ((mid < lo || mid >= hi) && !warned) { // a midpoint always lies in [lo, hi)
                System.out.println(name + " probe " + probes + ": mid = " + mid + " is outside [" + lo + ", " + hi + ")");
                warned = true;
            }
            if ((long) mid * mid < n) lo = mid + 1;
            else hi = mid;
        }
        System.out.println(name + " k = " + lo + " after " + probes + " probes");
    }

    public static void main(String[] args) {
        long n = 3_000_000_000_000_000_000L;
        search("(lo + hi) / 2      ", (lo, hi) -> (lo + hi) / 2, n);
        search("lo + (hi - lo) / 2 ", (lo, hi) -> lo + (hi - lo) / 2, n);
        search("(lo + hi) >>> 1    ", (lo, hi) -> (lo + hi) >>> 1, n);
    }
}

// The smallest whole number k with k * k >= n, searched for between 0 and 2,000,000,000 with three midpoints.
#include <cstdint>
#include <cstdio>
#include <numeric>
#include <print>

template <class Midpoint>
void search(const char* name, Midpoint midpoint, std::int64_t n) {
    int lo = 0, hi = 2'000'000'000;
    int probes = 0;
    bool warned = false;
    // Invariant: every k below lo has k * k < n, every k from hi on has k * k >= n.
    while (lo < hi) {
        if (++probes > 64) {  // 31 probes settle 2,000,000,000 values, so 64 means something is wrong
            std::println("{} still searching after 64 probes: lo = {}, hi = {}", name, lo, hi);
            return;
        }
        int mid = midpoint(lo, hi);
        if ((mid < lo || mid >= hi) && !warned) {  // a midpoint always lies in [lo, hi)
            std::println("{} probe {}: mid = {} is outside [{}, {})", name, probes, mid, lo, hi);
            warned = true;
        }
        if (std::int64_t{mid} * mid < n) lo = mid + 1;
        else hi = mid;
    }
    std::println("{} k = {} after {} probes", name, lo, probes);
}

int main() {
    std::setvbuf(stdout, nullptr, _IONBF, 0);  // the sanitizer reports on standard error: keep both in order
    const std::int64_t n = 3'000'000'000'000'000'000;
    search("(lo + hi) / 2        ", [](int lo, int hi) { return (lo + hi) / 2; }, n);
    search("lo + (hi - lo) / 2   ", [](int lo, int hi) { return lo + (hi - lo) / 2; }, n);
    search("std::midpoint(lo, hi)", [](int lo, int hi) { return std::midpoint(lo, hi); }, n);
}

from session import run

# The same search with three midpoints in each language; the C++ build reports undefined behaviour as it happens.
run("""
java SquareRoot.java
clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined square_root.cpp -o square_root && ./square_root
""")

$ java SquareRoot.java
(lo + hi) / 2       probe 2: mid = -647483647 is outside [1000000001, 2000000000)
(lo + hi) / 2       still searching after 64 probes: lo = -863311528, hi = 2000000000
lo + (hi - lo) / 2  k = 1732050808 after 31 probes
(lo + hi) >>> 1     k = 1732050808 after 31 probes
$ clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined square_root.cpp -o square_root && ./square_root
square_root.cpp:32:69: runtime error: signed integer overflow: 1000000001 + 2000000000 cannot be represented in type 'int'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior square_root.cpp:32:69 
(lo + hi) / 2         probe 2: mid = -647483647 is outside [1000000001, 2000000000)
(lo + hi) / 2         still searching after 64 probes: lo = -863311528, hi = 2000000000
lo + (hi - lo) / 2    k = 1732050808 after 31 probes
std::midpoint(lo, hi) k = 1732050808 after 31 probes

The faulty midpoint fails on the second probe. The first probe sets lo to 1,000,000,001, and lo + hi would then be 3,000,000,001, which does not fit in an int. Java’s language specification says that its integer operators never signal overflow: the sum wraps around to −1,294,967,295, and half of it, −647,483,647, lies far outside [lo, hi). From there the invariant no longer holds, the search jumps backwards, and it settles into a cycle that the 64-probe guard stops. C++ does not define signed overflow at all; UndefinedBehaviorSanitizer reports the exact addition and its line, and a build without the sanitizer would report nothing. The safe midpoints finish in 31 probes, the bound for 2,000,000,000 candidates.

• lo + (hi - lo) / 2 works in every language, because it never forms a value larger than hi.
• Java: (lo + hi) >>> 1. The unsigned shift reads the wrapped 32-bit sum as an unsigned number, which is exact up to 4,294,967,295, so the result is right whenever lo and hi are not negative. The JDK’s own search uses it.
• C++20: std::midpoint(lo, hi) from <numeric> cannot overflow. For an odd sum it rounds towards its first argument, so with lo first it rounds down, as the template expects.
• Go: since Go 1.1, int is 64 bits on 64-bit platforms, so the sum of two values up to 2 × 10⁹ fits. With int32, or on a 32-bit platform, the specification says that signed overflow wraps without a panic, and the same cycle appears. sort.Search computes its midpoint as int(uint(i+j) >> 1).
• JavaScript numbers are exact for whole numbers up to Number.MAX_SAFE_INTEGER, 2⁵³ − 1, so Math.floor((lo + hi) / 2) is safe. The shift operators are not: >> first turns its left side into a signed 32-bit integer, so (lo + hi) >> 1 goes negative once the sum passes 2,147,483,647, while >>> converts to an unsigned 32-bit integer and stays right below 2³².

"""The same search in Python, whose integers have no fixed size, so lo + hi cannot overflow."""


def ceil_sqrt(n):
    """The smallest whole number k with k * k >= n, for 0 <= n <= 4 * 10**18."""
    lo, hi = 0, 2_000_000_000
    probes, largest_sum = 0, 0
    # Invariant: every k below lo has k * k < n, every k from hi on has k * k >= n.
    while lo < hi:
        probes += 1
        largest_sum = max(largest_sum, lo + hi)
        mid = (lo + hi) // 2
        if mid * mid < n:
            lo = mid + 1
        else:
            hi = mid
    return lo, probes, largest_sum


n = 3 * 10**18
k, probes, largest_sum = ceil_sqrt(n)
print(f"k = {k} after {probes} probes")
print(f"(k - 1)**2 < n <= k**2: {(k - 1) ** 2 < n <= k**2}")
print(f"largest lo + hi formed: {largest_sum:,}; a 32-bit int stops at {2**31 - 1:,}")

k = 1732050808 after 31 probes
(k - 1)**2 < n <= k**2: True
largest lo + hi formed: 3,500,000,001; a 32-bit int stops at 2,147,483,647

// Four ways to halve lo + hi in JavaScript. Numbers are 64-bit floating point, exact for whole numbers up to
// 2 ** 53, but >> first turns its left side into a 32-bit signed integer and >>> into a 32-bit unsigned one.
const lo = 1_000_000_001;
const hi = 2_000_000_000;
console.log(`lo = ${lo}, hi = ${hi}, lo + hi = ${lo + hi}`);
console.log(`(lo + hi) >> 1             ${(lo + hi) >> 1}`);
console.log(`(lo + hi) >>> 1            ${(lo + hi) >>> 1}`);
console.log(`Math.floor((lo + hi) / 2)  ${Math.floor((lo + hi) / 2)}`);
console.log(`lo + ((hi - lo) >>> 1)     ${lo + ((hi - lo) >>> 1)}`);

lo = 1000000001, hi = 2000000000, lo + hi = 3000000001
(lo + hi) >> 1             -647483648
(lo + hi) >>> 1            1500000000
Math.floor((lo + hi) / 2)  1500000000
lo + ((hi - lo) >>> 1)     1500000000

Python finds the same 1,732,050,808 in 31 probes, and the largest sum it formed, 3,500,000,001, would not have fitted in an int. The JavaScript lines halve the very sum that broke the Java search, and only >> gets it wrong.

This is not a classroom curiosity. A bug report against the JDK’s own Arrays.binarySearch showed a search of a byte array with 1.1 billion elements throwing ArrayIndexOutOfBoundsException at the index −1,064,671,149, because the midpoint was computed as (low + high) >> 1. The fix was the unsigned shift, and the JDK source computes (low + high) >>> 1 today.

The libraries: Python, Java, C++ and Go

"""Python's bisect module on the scores: both bounds, first and last positions, counts, and key=."""

from bisect import bisect_left, bisect_right

scores = [35, 42, 42, 58, 61, 61, 61, 77, 90]
first, end = bisect_left(scores, 61), bisect_right(scores, 61)
print(f"bisect_left(scores, 61) = {first}, bisect_right(scores, 61) = {end}")
print(f"61 sits at positions {list(range(first, end))}: {end - first} copies, the last at {end - 1}")
print(f"for 60, which is absent, both return {bisect_left(scores, 60)} and {bisect_right(scores, 60)}")
print(f"scores from 40 to 60: {bisect_right(scores, 60) - bisect_left(scores, 40)}")

# key= (Python 3.10 and later) searches records by one field, without a separate list of that field.
results = [("Asha", 35), ("Ravi", 42), ("Meera", 58), ("Kabir", 61), ("Zoya", 90)]  # sorted by score
i = bisect_left(results, 60, key=lambda r: r[1])
print(f"first record with a score of at least 60: {results[i]}")

bisect_left(scores, 61) = 4, bisect_right(scores, 61) = 7
61 sits at positions [4, 5, 6]: 3 copies, the last at 6
for 60, which is absent, both return 4 and 4
scores from 40 to 60: 3
first record with a score of at least 60: ('Kabir', 61)

import java.util.Arrays;

// What Java's Arrays.binarySearch returns for a value that repeats and for values that are missing.
public class Library {
    public static void main(String[] args) {
        int[] a = {10, 20, 20, 20, 30};
        System.out.println("binarySearch(a, 20) = " + Arrays.binarySearch(a, 20) + " (the 20s are at 1, 2 and 3)");
        for (int key : new int[] {25, 5, 35}) {
            int r = Arrays.binarySearch(a, key);
            System.out.println("binarySearch(a, " + key + ") = " + r + ", so the insertion point -(r + 1) is " + (-(r + 1)));
        }
    }
}

// The C++ library's bounds on a value that repeats and on values that are missing.
#include <algorithm>
#include <print>
#include <vector>

int main() {
    const std::vector<int> a{10, 20, 20, 20, 30};
    auto at = [&](auto it) { return it - a.begin(); };
    std::println("lower_bound(20) = {}, upper_bound(20) = {}", at(std::lower_bound(a.begin(), a.end(), 20)),
                 at(std::upper_bound(a.begin(), a.end(), 20)));
    auto [first, last] = std::equal_range(a.begin(), a.end(), 20);
    std::println("equal_range(20) = [{}, {}): 20 occurs {} times", at(first), at(last), last - first);
    std::println("lower_bound(25) = {}, binary_search(25) = {}", at(std::lower_bound(a.begin(), a.end(), 25)),
                 std::binary_search(a.begin(), a.end(), 25));
    std::println("ranges::lower_bound(a, 35) = {}, which is a.size()", at(std::ranges::lower_bound(a, 35)));
}

from session import run

# The library searches of Java and C++ on the same five values.
run("""
java Library.java
clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined library.cpp -o library && ./library
""")

$ java Library.java
binarySearch(a, 20) = 2 (the 20s are at 1, 2 and 3)
binarySearch(a, 25) = -5, so the insertion point -(r + 1) is 4
binarySearch(a, 5) = -1, so the insertion point -(r + 1) is 0
binarySearch(a, 35) = -6, so the insertion point -(r + 1) is 5
$ clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined library.cpp -o library && ./library
lower_bound(20) = 1, upper_bound(20) = 4
equal_range(20) = [1, 4): 20 occurs 3 times
lower_bound(25) = 4, binary_search(25) = false
ranges::lower_bound(a, 35) = 5, which is a.size()

• Python. bisect_left is the lower bound and bisect_right the upper bound. Since Python 3.10 both take key=, which is applied to the list’s elements but not to x, so a list of records can be searched by one field without a second list. insort finds its position in O(log n) and then inserts into the list in O(n), as the documentation warns, so n insertions cost O(n²).
• Java. Arrays.binarySearch answers a different question: is the key present, and where is one copy of it? It is the closed-range search, which returns as soon as a probe equals the key, so its documentation promises no particular copy when values repeat; here it returned 2, the middle of three 20s. A missing key comes back as −(insertion point) − 1, which is negative exactly when the key is absent, and −(r + 1) recovers the insertion point. On an unsorted array the results are undefined. Java has no lower bound for arrays, so write the template.
• C++. std::lower_bound and std::upper_bound are the two bounds. They return iterators, last when no element qualifies, and std::equal_range returns both bounds at once, while std::binary_search only says whether the value is there. The range must be partitioned by the comparison, and each search makes at most log₂(N) + O(1) comparisons. On a std::set or a std::map, whose iterators are not random access, call their member lower_bound instead.
• Go, which this page does not run: slices.BinarySearch(s, x) returns the earliest position where x is found, or where it would go, together with whether it was found, so it is a lower bound with a flag. sort.Search(n, f) returns the first index in [0, n) at which f is true, or n: the template itself, for any condition that flips once.
• JavaScript has no binary search in the language: indexOf, includes and findIndex look at the elements one at a time from the start. Write the template, as cutoff.mjs does.

Practise: write both bounds

Write lower_bound and upper_bound from their invariants, without bisect. The sample tests cover the inputs where binary searches usually fail, and the last one compares both functions with bisect on 2,000 random lists.

scores = [35, 42, 42, 58, 61, 61, 61, 77, 90]
lower_bound(scores, 61)  # 4: the first 61
upper_bound(scores, 61)  # 7: the first value after the last 61
lower_bound(scores, 99)  # 9: nothing is that large

def lower_bound(a, x):
    """The first position whose value is at least x, or len(a) if there is none."""
    # Replace this line with your loop.
    return 0


def upper_bound(a, x):
    """The first position whose value is greater than x, or len(a) if there is none."""
    # Replace this line with your loop.
    return len(a)

import ast
import bisect
import random

import bounds
from bounds import lower_bound, upper_bound

SCORES = [35, 42, 42, 58, 61, 61, 61, 77, 90]


def test_repeated_value():
    """61 appears three times: the lower bound is its first copy, the upper bound just past its last"""
    assert lower_bound(SCORES, 61) == 4
    assert upper_bound(SCORES, 61) == 7


def test_absent_value():
    """for a value that is not there, both bounds are where it would go"""
    assert lower_bound(SCORES, 60) == 4
    assert upper_bound(SCORES, 60) == 4


def test_empty_list():
    """an empty list has nothing at or above x"""
    assert lower_bound([], 5) == 0
    assert upper_bound([], 5) == 0


def test_x_below_every_value():
    """every value is at least x, and greater than x"""
    assert lower_bound(SCORES, 0) == 0
    assert upper_bound(SCORES, 0) == 0


def test_x_above_every_value():
    """no value qualifies, so both return len(a)"""
    assert lower_bound(SCORES, 91) == 9
    assert upper_bound(SCORES, 91) == 9


def test_every_value_equal():
    """[7, 7, 7] searched for 7: the bounds are the two ends"""
    assert lower_bound([7, 7, 7], 7) == 0
    assert upper_bound([7, 7, 7], 7) == 3


def test_single_value():
    """a list of one value, searched below, at and above it"""
    assert [lower_bound([5], x) for x in (4, 5, 6)] == [0, 0, 1]
    assert [upper_bound([5], x) for x in (4, 5, 6)] == [0, 1, 1]


def test_list_not_changed():
    """the search only reads the list"""
    values = [1, 2, 2, 3]
    lower_bound(values, 2)
    upper_bound(values, 2)
    assert values == [1, 2, 2, 3]


def test_against_bisect():
    """2,000 random sorted lists, compared with bisect_left and bisect_right"""
    rng = random.Random(11)
    for _ in range(2_000):
        a = sorted(rng.randint(0, 6) for _ in range(rng.randint(0, 10)))
        x = rng.randint(-1, 7)
        assert lower_bound(a, x) == bisect.bisect_left(a, x), f"lower_bound({a}, {x})"
        assert upper_bound(a, x) == bisect.bisect_right(a, x), f"upper_bound({a}, {x})"


def test_searches_by_itself():
    """the searches are your own: no bisect, and no index(), count() or sort calls"""
    with open(bounds.__file__, encoding="utf-8") as source:
        tree = ast.parse(source.read())
    used = []
    for node in ast.walk(tree):
        if isinstance(node, ast.Import):
            used += [alias.name for alias in node.names if alias.name == "bisect"]
        elif isinstance(node, ast.ImportFrom) and node.module == "bisect":
            used.append("bisect")
        elif isinstance(node, ast.Call):
            name = node.func.attr if isinstance(node.func, ast.Attribute) else getattr(node.func, "id", None)
            if name in ("index", "sorted", "sort", "count"):
                used.append(f"{name}()")
    assert used == [], f"write the binary searches yourself, without {', '.join(used)}"

Interview questions

Why do Java and C++ solutions write mid = lo + (hi - lo) / 2 instead of (lo + hi) / 2, and does Python need the same care?

The sum lo + hi can pass the largest int, 2,147,483,647, before it is halved. Java then wraps it to a negative number without any warning, so mid lands outside the range: an array read throws, and a search over a range of answers can loop for ever. In C++ signed overflow is undefined behaviour. lo + (hi - lo) / 2 never forms a value larger than hi, so it is safe whenever lo and hi are; Java can also write (lo + hi) >>> 1, and C++20 has std::midpoint. Arrays of a billion elements are rare in a round, but answer ranges up to 2 × 10⁹ are common, and there the bug is real. Python’s integers have no fixed size, so (lo + hi) // 2 is always exact.

What do lower bound and upper bound return for a value that appears several times, and for a value that is absent?

The lower bound is the first position whose value is at least x, and the upper bound the first position whose value is greater than x. For a value with several copies, the lower bound points at the first copy and the upper bound just past the last, so the copies fill the positions from lower to upper − 1 and there are upper − lower of them. For an absent value both return the same position: where x would be inserted to keep the list sorted, which is also the number of values below x. That position can be n, one past the end, when every value is smaller, so check it before reading a[i].

Key takeaways

• Derive every boundary from one invariant: a[:lo] is below x, a[hi:] is x or more, and a[lo:hi] is unknown. The loop is while lo < hi with lo = mid + 1 or hi = mid.
• Every pass at least halves the unknown part, so the loop ends after at most ⌊log₂ n⌋ + 1 passes: 30 for a billion values, as measured.
• The upper bound changes one comparison. First and last positions and counts are bounds or differences of bounds, each with a check for n and −1.
• Every small input is a cheap test: 756 cases expose lo = mid, hi = mid - 1 and a mixed while lo <= hi at once.
• In Java and C++ write lo + (hi - lo) / 2, (lo + hi) >>> 1 or std::midpoint: the plain sum broke a search over 2,000,000,000 answers on its second probe.
• Know what each library promises: bisect_left, std::lower_bound and slices.BinarySearch are lower bounds, while Java’s Arrays.binarySearch may return any copy of a repeated value.