Programming

Binary Search: How It Works and How to Write It Correctly

Binary search finds a value among a billion in 30 steps. Learn a bug-free pattern and apply it to arrays, square roots, and git bisect.

·
10 min read
·
AI-assisted

AI tooling disclosure

Generative AI materially contributed to this article.

Human review confirmed by the author.

Binary Search: How It Works and How to Write It Correctly

TL;DR

  • Binary search finds a value in a sorted array by repeatedly throwing away half of what is left: 30 steps for a billion items, 40 for a trillion.

  • It is famously easy to get wrong. In Jon Bentley's classes, about 90% of professional programmers wrote a buggy version, and the binary search in Java's own standard library carried an overflow bug for years.

  • The safe way is to write one loop that finds the first index where a yes/no question turns true, keep an invariant, and build everything else on it in one line each.

  • The same loop solves any monotonic question: integer square roots, thresholds, and git bisect.

1. The idea

Think of a number between 1 and 100 and I will guess it in at most 7 guesses, if you tell me "higher" or "lower" each time. I guess 50. You say "higher". Now the answer is in 51 to 100, so I guess 75. Every answer throws away half the candidates.

A sorted array works the same way. Compare the middle element with your target, and one comparison tells you which half cannot contain it. Because the work halves each time, the number of steps grows like log₂ n. We measured the exact worst case of the loop below:

Items in the array

Worst-case steps (binary search)

Worst-case steps (linear scan)

10

4

10

100

7

100

1,000

10

1,000

1,000,000

20

1,000,000

1,000,000,000

30

1,000,000,000

1,000,000,000,000

40

1,000,000,000,000

Doubling the data adds exactly one step. That is the entire appeal.

It has two requirements: the data must be sorted, and you must be able to jump to the middle in constant time (an array, not a linked list).


2. Write it once, correctly

Most explanations teach "find this value." That framing causes trouble: what do you return when the value is absent, and which copy do you find when there are duplicates?

A sturdier framing is to look for a boundary. Imagine a yes/no question that is false for the first part of the array and true for the rest, such as "is a[i] at least 23?" Binary search finds the first index where the answer is true. That index always exists (it might be the end of the array), so there is no special "not found" path inside the loop.

// bsearch.mjs: binary search, built on one function.

// The first index in [lo, hi) where pred(index) is true. This assumes pred is false for
// a prefix of the range and true for the rest. If it is never true, the answer is hi.
export function firstTrue(lo, hi, pred) {
  // Invariant: pred is false for every index before lo, and true for every index from hi on.
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);   // never overflows, never negative
    if (pred(mid)) hi = mid;                      // mid might be the answer, so keep it
    else lo = mid + 1;                            // mid is too small, so drop it
  }
  return lo;                                      // lo === hi: the boundary
}

// Everything else is a one-line question to firstTrue, on a sorted array a:
export const lowerBound = (a, x) => firstTrue(0, a.length, (i) => a[i] >= x);   // first index with a[i] >= x
export const upperBound = (a, x) => firstTrue(0, a.length, (i) => a[i] > x);    // first index with a[i] >  x
export const count = (a, x) => upperBound(a, x) - lowerBound(a, x);              // how many times x occurs

export function search(a, x) {                                                   // index of the first x, or -1
  const i = lowerBound(a, x);
  return i < a.length && a[i] === x ? i : -1;
}
flowchart TD
    S["lo = 0, hi = n"] --> L{"lo < hi ?"}
    L -->|"no"| R["Return lo<br/>the boundary"]
    L -->|"yes"| M["mid = lo + floor((hi − lo) / 2)"]
    M --> P{"pred(mid) is true?"}
    P -->|"true: the answer is mid or to its left"| H["hi = mid"]
    P -->|"false: the answer is to the right of mid"| O["lo = mid + 1"]
    H --> L
    O --> L

The whole algorithm rests on the invariant in the comment. At every moment the array splits into three zones:

index:  0                    lo                     hi                      n
        [ pred is FALSE      ][ not checked yet     ][ pred is TRUE         ]
        [ for sure           ][                     ][ for sure             ]

Each iteration checks one element in the middle zone and moves a boundary past it, so the middle zone shrinks. When it is empty (lo === hi), the two proven zones touch, and the boundary between them is the answer. Four small decisions keep it correct:

  • Half-open range [lo, hi). hi points one past the last candidate. That makes an empty array (hi = 0) work with no special case.

  • hi = mid but lo = mid + 1. When pred(mid) is true, mid itself could be the answer, so keep it. When it is false, mid is ruled out, so skip it. Both updates strictly shrink the range, so the loop always ends.

  • The midpoint is lo + floor((hi − lo) / 2), not (lo + hi) / 2. We will see why in section 4.

  • One loop, one exit. There is no early return inside the loop. That is what keeps duplicates under control.


3. Everything else is one line

Once firstTrue is right, the familiar operations are one-line questions on a sorted array a:

  • lowerBound(a, x) is the first index with a[i] >= x.

  • upperBound(a, x) is the first index with a[i] > x.

  • count(a, x) is the difference between them.

  • search(a, x) checks whether the element at lowerBound really equals x.

These are exactly the semantics of Python's standard library: bisect_left returns the insertion point that splits the list so everything to its left is < x and everything from it on is >= x, and bisect_right does the same with <= and >. lowerBound is also the insertion point: the index where x would go to keep the array sorted. (Java's Arrays.binarySearch reports a miss as -(insertion point) - 1, so you can still recover it.)

Here is a real trace of lowerBound(a, 23) on [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]:

Step

lo

hi

mid

a[mid]

a[mid] >= 23

Update

1

0

10

5

23

true

hi = 5

2

0

5

2

8

false

lo = 3

3

3

5

4

16

false

lo = 5

The loop ends with lo = hi = 5, and a[5] is 23, found in three steps instead of six. Searching for 24, which is absent, ends at index 6 (the insertion point), and search reports -1 because a[6] is 38, not 24.


4. The three classic bugs

In his book Programming Pearls, Jon Bentley reports that the first binary search was published in 1946, but the first version that worked for every array size did not appear until 1962. (Some accounts date the first general version to 1960, by Derrick Lehmer. Either way, it took about fifteen years.) When he gave professional programmers a couple of hours to write one, about 90% of them had bugs in their code. Knuth observed that although the idea is simple, the details are surprisingly tricky. Here are the traps, each one demonstrated.

Bug 1: the midpoint overflows

The textbook line is mid = (low + high) / 2. In languages with 32-bit integers, low + high can exceed the largest integer and wrap around to a negative number. Josh Bloch, who wrote the binary search in Java's java.util.Arrays, described how that exact line sat in the JDK and in Bentley's proven-correct textbook version, and broke for arrays of about a billion elements (2³⁰) or more. It had lain in wait for years because such arrays used to be unthinkable.

JavaScript's plain numbers are 64-bit floats, so lo + hi itself is safe, but the bitwise operators convert to 32-bit integers and bring the bug right back:

const lo = 1_500_000_000, hi = 2_000_000_000;
console.log((lo + hi) >> 1);          // -397483648   (the sum wrapped around in 32-bit arithmetic)
console.log(lo + ((hi - lo) >> 1));   //  1750000000   (correct)

We ran a search over a virtual 3,000,000,000-element range with the >> 1 midpoint. It never converged: the midpoint went negative and the search wandered below zero for 200 steps, when a correct search needs only 32. The fix is a single idea: compute the distance between the ends, not their sum.

Bug 2: the loop that never ends

The mirror-image trap is moving a boundary to mid when it must move past it:

function stuck(a, x) {
  let lo = 0, hi = a.length - 1;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (a[mid] < x) lo = mid;       // BUG: must be mid + 1, or the range can stop shrinking
    else hi = mid;
  }
  return lo;
}

With [1, 3] and x = 3, lo is 0, hi is 1, mid is 0, and lo = mid changes nothing. The range never shrinks. (We confirmed it: after 1,000 iterations it was still at lo = 0, hi = 1.) This is why firstTrue uses mid + 1 on one side and mid on the other, and why the invariant says exactly which zone each side owns.

Bug 3: duplicates

The classic version returns as soon as it sees a match:

function classic(a, x) {
  let lo = 0, hi = a.length - 1;
  while (lo <= hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (a[mid] === x) return mid;   // stops at whichever copy it lands on
    if (a[mid] < x) lo = mid + 1; else hi = mid - 1;
  }
  return -1;
}

classic([1, 2, 2, 2, 2, 2, 2, 3], 2);   // 3, not 1

It finds a 2, whichever one the midpoint happens to hit, not the first. With the array above, it returns index 3, while lowerBound returns 1 and upperBound returns 7, so count is 6. If you need "the first," "the last," or "how many," the boundary formulation answers all three without extra code.


5. Binary search on the answer

The loop never uses the array. It only asks pred(i) for the middle index. So it works on anything where a yes/no question flips from false to true exactly once.

Integer square root. What is the largest x with x * x <= n? The question "is x * x > n?" is false for small x and true for large x:

import { firstTrue } from './bsearch.mjs';

const isqrt = (n) => firstTrue(0, n + 1, (x) => x * x > n) - 1;

isqrt(99);    // 9
isqrt(1e12);  // 1000000

We checked it against the defining property r² ≤ n < (r + 1)² on 100,015 values up to 9 × 10¹⁵ and found no violations. Even for 9 × 10¹⁵ it takes only 53 steps.

Finding the commit that broke your build. git bisect is binary search over your history: commits are the indices, and "is the bug present?" is the predicate. Git's own documentation describes it as using a binary search algorithm to find the commit that introduced a bug, and git bisect run automates the questions with a script. We built a 128-commit repository where the bug appears at commit 87 and let git find it:

Test

Commit git checked out

Result

First bad commit must be in (candidates)

1

commit 64

works

65 to 128 (64)

2

commit 96

bug present

65 to 96 (32)

3

commit 80

works

81 to 96 (16)

4

commit 88

bug present

81 to 88 (8)

5

commit 84

works

85 to 88 (4)

6

commit 86

works

87 to 88 (2)

7

commit 87

bug present

87 to 87 (1)

It took 7 tests instead of up to 87 for a linear scan, and it found commit 87. The candidates halved every time: 64, 32, 16, 8, 4, 2, 1.

The recipe is always the same: find a point where the answer is "no" and a point where it is "yes," then call firstTrue. The catch is that the question must be monotonic. If a bug comes and goes between commits, git bisect can point at the wrong one, because its assumption is broken.


6. When not to use it

  • Unsorted data, searched once. Sorting costs O(n log n) and a scan costs O(n), so for a one-off lookup just scan. Binary search pays off when you sort once and search many times.

  • No constant-time indexing. In a linked list, reaching the middle costs O(n), which wipes out the savings.

  • Exact lookups only. A hash table answers "is this key present?" in constant time on average. Binary search wins when you need order: nearest value, insertion point, range counts.

  • Frequently changing data. Inserting into a sorted array is O(n). Python's own documentation notes that for insort, the O(log n) search is dominated by the slow O(n) insertion. Use a balanced tree or a database index instead.

  • Tiny arrays. For a handful of elements, a plain scan is simpler and just as good.


7. How to test it

Bentley's lesson, and Bloch's, is that proving a binary search correct is not enough: you have to run it. The cheapest strong test compares it with brute force on thousands of random inputs, deliberately including empty arrays and many duplicates:

import { lowerBound, upperBound, search, count } from './bsearch.mjs';

const rnd = (n) => Math.floor(Math.random() * n);
for (let t = 0; t < 100_000; t++) {
  const a = Array.from({ length: rnd(41) }, () => rnd(16)).sort((p, q) => p - q);  // empty arrays, many duplicates
  const x = rnd(18) - 1;                                                            // below, inside and above the range
  const lb = a.findIndex((v) => v >= x), ub = a.findIndex((v) => v > x);
  const want = { lb: lb === -1 ? a.length : lb, ub: ub === -1 ? a.length : ub,
                 first: a.indexOf(x), n: a.filter((v) => v === x).length };
  if (lowerBound(a, x) !== want.lb || upperBound(a, x) !== want.ub ||
      search(a, x) !== want.first || count(a, x) !== want.n)
    throw new Error(`mismatch: ${JSON.stringify(a)} x=${x}`);
}
console.log('all cases agree with brute force');

We ran 200,000 such cases and got 0 mismatches. We also compared lowerBound and upperBound with Python's standard-library bisect_left and bisect_right on 50,000 random arrays: 0 mismatches. And for every array size from 1 to 2,000, the worst case was exactly ⌈log₂(n + 1)⌉ steps.


8. The mental model on one screen

  1. Binary search finds a boundary in sorted data, throwing away half the candidates at each step.

  2. Write one loop, firstTrue, with a half-open range and an invariant, and build lowerBound, upperBound, count and search on top of it.

  3. Use mid = lo + floor((hi − lo) / 2), and move boundaries with hi = mid and lo = mid + 1.

  4. It works on any monotonic yes/no question, not just arrays: square roots, thresholds, git bisect.

  5. It needs sorted data and fast indexing, and it only pays off when you search more than once.

  6. Test it against brute force, with duplicates and empty inputs.


Further reading

If this post helped, send it to the teammate who still writes (low + high) / 2.

Comments(0)

Join the discussion by logging into your account.

No comments yet. Be the first to comment!

Alysaa Lissy

Passionate developer sharing knowledge about modern web technologies and best practices.

Subscribe to Alysaa Lissy's Newsletter

Direct email dispatches when new stories are published. Zero algorithms.