Implementation

This chapter builds the basic component of searching, lower_bound, as a clean Python function and explains it line by line. Then the same routine is ported to C++, Java and TypeScript, together with the standard functions each language already ships and the overflow trap in computing the middle index.

Python implementation

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


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


def contains(a, x):
    i = lower_bound(a, x)
    return i < len(a) and a[i] == x

Line by line:

• lo=0, hi=None: the half-open search range [lo, hi). It defaults to the whole array, and like the bisect module the caller can restrict it to a slice.
• while lo < hi: loop while at least one candidate remains. Once lo == hi, that position is the answer.
• mid = (lo + hi) // 2: the middle index. Python integers are unbounded, so the sum cannot overflow.
• if a[mid] < x: lo = mid + 1: if the middle value is smaller than x, neither mid nor anything left of it can be the answer, so discard them.
• else: hi = mid: if the middle value is at least x, mid itself might be the answer, so keep it and discard only the right side.
• return lo: at the end, lo is the first index with a[i] >= x, or len(a) when no such element exists.

upper_bound differs in a single comparison (< becomes <=). contains checks that the lower_bound position is inside the array and holds exactly x. The bounds check must come first, otherwise an IndexError is possible.

Checking against the standard library

When you write your own version, randomized comparison against a trusted implementation is the most reliable test.

import random
from bisect import bisect_left, bisect_right

for _ in range(10_000):
    a = sorted(random.randint(0, 20) for _ in range(random.randint(0, 15)))
    x = random.randint(-1, 21)
    assert lower_bound(a, x) == bisect_left(a, x)
    assert upper_bound(a, x) == bisect_right(a, x)
    assert contains(a, x) == (x in a)
print("ok")

Edge cases such as empty arrays, targets below or above every element, and arrays of identical values show up naturally in random inputs. Since Python 3.10 you can also pass a key, as in bisect_left(records, 30, key=lambda r: r.age).

C++

#include <cstddef>
#include <vector>

std::size_t lower_bound_index(const std::vector<int>& a, int x) {
    std::size_t lo = 0, hi = a.size();
    while (lo < hi) {
        std::size_t mid = lo + (hi - lo) / 2;
        if (a[mid] < x) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

The C++ standard library already has std::lower_bound(a.begin(), a.end(), x), which returns an iterator; subtract a.begin() to get an index. There is also std::upper_bound, std::equal_range for both boundaries at once, and std::partition_point for the boundary of an arbitrary predicate.

Java

public final class Search {
    public static int lowerBound(int[] a, int x) {
        int lo = 0, hi = a.length;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (a[mid] < x) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }
}

Java's Arrays.binarySearch returns the index when the key is found and -(insertion point) - 1 when it is not. With duplicates it makes no promise about which occurrence it returns, so when you need the first one, a hand-written lower_bound like the one above is the safer choice.

TypeScript

export function lowerBound(a: readonly number[], x: number): number {
  let lo = 0;
  let hi = a.length;
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (a[mid] < x) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

console.log(lowerBound([1, 2, 2, 2, 3, 5], 2)); // 1

JavaScript has no standard binary search for arrays, so you will often write one like this. Numbers are 64-bit floats, so lo + hi cannot overflow, but (lo + hi) >> 1 converts to a signed 32-bit integer and can go wrong for very large values. For arrays of strings or objects, generalize the function to take a comparator.

The middle index and overflow

In languages with fixed-size integers such as C, C++ and Java, (lo + hi) / 2 can overflow when lo and hi are both large. Java's own Arrays.binarySearch carried exactly this bug for years until it was fixed in 2006. There are two safe options:

• lo + (hi - lo) / 2: add half of the difference, which never exceeds hi.
• Java's (lo + hi) >>> 1: an unsigned right shift yields the correct value even if the sum wraps negative (as long as lo and hi are non-negative).

Summary

• Use lower_bound over a half-open interval, with only the updates lo = mid + 1 and hi = mid, as your basic building block.
• upper_bound changes one comparison; membership is checked from the lower_bound result.
• Every language ships a standard version (bisect, std::lower_bound, Arrays.binarySearch); check its return convention before relying on it.
• In fixed-width integer languages, compute the middle as lo + (hi - lo) / 2 to avoid overflow.