Binary search
Overview
Binary search inspects the middle element of a sorted range and rules out the half that cannot hold the target. Rather than scanning an alphabetized roster from the first line, you open it near the middle and skip the entire earlier or later half in one comparison.
History
John Mauchly gave one of the earliest published accounts of binary search during the 1946 Moore School Lectures. Early formulations worked cleanly only when the table length had the form ; Derrick H. Lehmer published a general routine for arbitrary lengths in 1960, and Hermann Bottenbruch presented a variant in 1962 that deferred the equality test until the loop terminated, saving one comparison per iteration.1
In his 1983 paper “Writing Correct Programs,” Jon Bentley used binary search to show how easily boundary conditions go wrong even for seasoned programmers, separating initialization, loop invariants, and termination.2 Two decades later, in 2006, Joshua Bloch showed that his own java.util.Arrays.binarySearch implementation in the JDK could overflow signed 32-bit integers when computing (low + high) / 2 on large arrays.3
Half-open intervals and loop invariants
Instead of asking only whether a key is present, it is cleaner to ask for the first index whose value is at least target. This position is the lower bound (or left insertion boundary). When duplicates exist, it points to the first copy; when the key is absent, it marks the index where target can be inserted without breaking the sort order. If every element is smaller than target, the boundary falls at the array length .
Represent the remaining candidate positions as a half-open interval that includes and excludes . Because an array of length has possible insertion boundaries ( through ), the search starts at and preserves the following invariant and midpoint rule:
Whenever , the midpoint satisfies . If , index is also too small, so advancing preserves the left invariant. Otherwise , so remains a valid candidate and setting preserves the right invariant. Either branch strictly shrinks , guaranteeing termination at .
Executable example
The array [1, 3, 3, 7, 9] exercises both a duplicate key (3) and a missing key (6). The caller must supply finite numbers sorted in ascending order; verifying sortedness inside the function would cost time and defeat the logarithmic search (see Guard Clauses).
function lowerBound(values: readonly number[], target: number): number {
let lo = 0;
let hi = values.length;
// Invariant: values[0..lo) < target and values[hi..n) >= target.
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (values[mid]! < target) lo = mid + 1;
else hi = mid;
}
return lo;
}
function indexOfSorted(values: readonly number[], target: number): number {
const index = lowerBound(values, target);
// An insertion boundary still needs an in-bounds equality check.
return index < values.length && values[index] === target ? index : -1;
}
const values = [1, 3, 3, 7, 9];
console.log(lowerBound(values, 3));
console.log(lowerBound(values, 6));
console.log(indexOfSorted(values, 6));Output:
1
3
-1The lower bound of 3 is index 1. For 6, the boundary lands at index 3 (which holds 7), so the equality check in indexOfSorted returns -1. Using Math.floor((hi - lo) / 2) avoids both endpoint-sum overflow and JavaScript’s 32-bit bitwise truncation.
C++ example
In C++20, std::span<const int> and std::size_t express the same half-open interval without copying the underlying container. Unsigned integer division lo + (hi - lo) / 2 truncates toward zero and produces the same boundary index as std::lower_bound.
#include <cstddef>
#include <iostream>
#include <span>
#include <vector>
std::size_t lowerBound(std::span<const int> values, int target) {
std::size_t lo = 0;
std::size_t hi = values.size();
// Invariant: values[0..lo) < target and values[hi..n) >= target.
while (lo < hi) {
std::size_t mid = lo + (hi - lo) / 2;
if (values[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo;
}
int indexOfSorted(std::span<const int> values, int target) {
std::size_t index = lowerBound(values, target);
// An insertion boundary still needs an in-bounds equality check.
return index < values.size() && values[index] == target
? static_cast<int>(index)
: -1;
}
int main() {
const std::vector<int> values{1, 3, 3, 7, 9};
std::cout << lowerBound(values, 3) << '\n';
std::cout << lowerBound(values, 6) << '\n';
std::cout << indexOfSorted(values, 6) << '\n';
return 0;
}Output:
1
3
-1Cost and practical boundaries
With random access and comparison, halving candidate positions takes time and auxiliary space.
Three practical boundaries matter in production. First, binary search requires random access; running it on a linked list degrades to because stepping to the midpoint walks the list. Second, finding an insertion index in does not make array insertion fast—shifting trailing elements still costs , so write-heavy workloads belong in a balanced search tree or B-tree. Third, floating-point arrays containing NaN violate total ordering because both < and >= evaluate to false; filter or reject NaN values before searching.
See also
Footnotes
- Donald E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd ed., Addison-Wesley, 1998, §6.2.1 ("Searching an Ordered Table"), pp.409–426. ↩
- Jon Bentley, “Writing Correct Programs,” Communications of the ACM 26(12), 1983, pp.1040–1045. Paper, DOI. ↩
- Joshua Bloch, “Extra, Extra — Read All About It: Nearly All Binary Searches and Mergesorts are Broken,” Google Research, 2006-06-02. Author’s article. ↩