Binary search

Yesterday everything worked, today it is broken, and hundreds of commits lie in between. Checking each is slow: build, run, look. But you do not need to check each. Take the middle: if it is already broken there, the culprit is in the first half; if not yet, in the second. Every check cuts off half of the suspects. Below is the real history of this site, 904 commits from February to October 2026. Pick a question—for example, when the maths textbook appeared—and see how many checks it takes.

Ten checks for 904 commits. Scanning from the first commit up to the maths textbook would take 484. On a million commits binary search would need twenty. This is the git bisect command: it works exactly like this, only the check is yours—you build the version it picked and say “good” or “bad”.

The idea

If the answer to “yes already?” changes exactly once along a row—first only “no”, then only “yes”—the boundary can be found by always asking about the middle of the remaining piece. One answer halves the piece, and after log₂ n questions a single point is left.

Note that this says nothing about numbers or sorting. All it needs is for the question to be monotone: if the textbook is in commit #483, it is in every later one too. A sorted array is a special case: for it the question “element ≥ x?” is monotone. So are “will k lorries be enough?”, “will the program fit in a second with n elements?”, “is the site broken in this version?”—and binary search works for all of them. The last case is covered in detail in binary search on the answer.

Lower and upper bounds

Most often binary search looks not for “is x in the array” but for a boundary: the first place where the element is not less than x. That position is called the lower bound. The first place where the element is strictly greater than x is the upper bound. Between them lie all the elements equal to x, and to the right of the lower bound lie all the elements not less than x.

Here are all the earthquakes of magnitude 5 and above in 2015–2025 from the USGS catalogue—19,073 of them, sorted by magnitude. How many were stronger than 7? Move the threshold and watch lo and hi close in on the answer.

The shaded band is everything we know nothing about yet. The code keeps one statement, an invariant: all elements left of lo are below the threshold, all elements from hi on are not. At the start lo = 0 and hi = n, and the statement holds because both sides are empty. Every step looks at the middle and moves one of the bounds so that the statement still holds. When lo and hi meet, nothing unknown is left, and lo is the answer.

Why the loop is right and finite

Take the middle mid = ⌊(lo + hi)/2⌋. While lo < hi, it lies in the half-open interval [lo, hi): mid ≥ lo and mid < hi.

• If a[mid] < x, every element left of mid is less than x too—the array is sorted. Move lo = mid + 1: the invariant “everything left of lo is less” still holds.
• Otherwise a[mid] ≥ x, and so is everything to its right. Move hi = mid: “everything from hi on is not less” still holds.

Either way the length hi − lo strictly decreases: in the first case lo grew by at least one, in the second hi became smaller than before. So the loop ends, and since the length nearly halves each time, there are at most ⌈log₂(n + 1)⌉ steps.

This is where almost every bug hides: write lo = mid instead of lo = mid + 1, and when hi = lo + 1 the middle equals lo, the length stops shrinking, and the loop never ends.

Code

Both bounds on the half-open interval [lo, hi). It is the most reliable form: the answer n (“no such element”) comes out by itself, with no special cases.

Standard libraries already have this. In Python, the bisect module: bisect_left(a, x) is the lower bound, bisect_right(a, x) the upper one. In Go, sort.Search(n, f): it finds the first index at which the function f becomes true, so it works with any monotone question, not only an array. For slices there is also slices.BinarySearch.

And this is git bisect over the site's history. Checking a commit here is a recorded answer rather than a build, but the search is the same:

Bugs everyone makes

Jon Bentley wrote in “Programming Pearls” about giving professional programmers on courses at Bell Labs and IBM the task of writing a binary search. They had plenty of time, yet only about one in ten ended up with correct code. The bugs repeat year after year:

• An endless loop. lo = mid with mid rounded down: on a piece of two elements the search stands still.
• Mixed conventions. A half-open [lo, hi) in one place and a closed [lo, hi] in another: then the loop either skips the last element or reads past the end of the array. Pick one convention and stick to it.
• Overflow. In Java and C, (lo + hi) / 2 overflows when lo + hi exceeds 2³¹ − 1. Such a bug lived for nine years in Arrays.binarySearch in Java's standard library until Joshua Bloch wrote about it in 2006. The safe form is lo + (hi - lo) / 2. Python integers do not overflow and Go's int is 64 bits, but the habit is a good one.
• Unsorted data. A binary search over an unsorted array finds nothing and reports no error—it just returns nonsense. If the array changes, sort it again or keep it in a search tree.

What it costs

Each check is a “yes” or “no”, exactly one bit of information. To tell n + 1 possible answers apart you need at least log₂(n + 1) bits, so binary search is optimal among all methods that learn about the data only through comparisons. Memory: a couple of variables.

There is a price too: the data must be ordered. Sorting costs O(n log n), and if you search only once, it is simpler to scan the array in O(n). Binary search wins when there are many searches, or when the order is there anyway—like commits in time.

History

The idea of binary search over a sorted table was mentioned by John Mauchly in the Moore School Lectures of 1946—one of the first programming courses in history. But, as Donald Knuth noted in “The Art of Computer Programming”, a version that works correctly for a table of any length appeared in print years later. A short algorithm that everyone understands at first sight turned out to be one of the hardest to write without bugs.

Problems

The first is lower and upper bounds on the same earthquakes. In the second the binary search runs not over an array but over numbers, and it is easy to fall into the floating-point trap.