sdlc.dev

Data structures and algorithms path · Finding things · Topic 7 of 13

Binary search and its bugs

Not started

Binary search finds a value in a sorted array by looking at the middle element and discarding the half that can't contain the answer, again and again, until one position is left. Each step halves the remaining range, so a billion items need about 30 comparisons. The idea fits in one sentence, but the details are where implementations go wrong: off-by-one bounds, infinite loops and, in some languages, integer overflow.

Why it matters: It finds anything in a sorted array of a billion items in about 30 steps, and it is famously easy to get subtly wrong.

  1. 1Sorted input, halving steps

    Compare with the middle element and throw away the half that can't contain the answer. O(log n) comparisons.

  2. 2Pick one invariant and keep it

    Decide what lo and hi mean (for example, a half-open range [lo, hi)) and make every line preserve exactly that.

  3. 3Find a boundary, not just a match

    Asking for the first index whose value is ≥ target handles duplicates, insertion points and "not found" in one function.

  4. 4Mind the midpoint

    In fixed-width integer arithmetic, (lo + hi) / 2 can overflow. lo + (hi - lo) / 2 cannot.

1

How it works

The explanation, with examples you can run.

Search for a boundary

The most useful form doesn't ask "is the target here?" but "where is the first element that is ≥ target?" That one function, usually called lower bound (bisect_left in Python, std::lower_bound in C++), answers several questions at once: whether the target is present, where its first copy is, and where it would be inserted to keep the array sorted.

⌘/Ctrl + Enter
OutputNot run yet

Press Run to see what your code prints, in order.

Runs in this browser, in an isolated frame with no access to this page. console.log, info, warn and error are shown; code runs as a classic script, so use an async function for await.

The invariant is: everything before lo is less than the target, and everything from hi onwards is greater than or equal to it. The answer is always in [lo, hi]. When arr[mid] < target, mid belongs to the "less than" part, so lo = mid + 1. Otherwise mid might be the answer, so hi = mid keeps it. Each iteration shrinks the range by at least one, so the loop ends, and when lo === hi that is the boundary.

The usual bugs

  • Mixed conventions. Using a closed range [lo, hi] (hi = length - 1, while (lo <= hi)) is fine, and so is a half-open one. Mixing their update rules skips elements or loops forever when two elements are left.
  • Returning any match. A "return as soon as arr[mid] === target" search finds a match. With duplicates you usually want the first or last.
  • Unsorted input. Binary search on data that isn't sorted by the same comparison returns nonsense without any error. Sort with the same comparator you search with.
  • Overflow. In Java, C and C++, (lo + hi) / 2 overflows when lo + hi exceeds the largest integer. Joshua Bloch wrote in 2006 that the JDK's own binarySearch had this bug, and it only appeared for arrays of about 2³⁰ elements. JavaScript numbers are doubles, so Math.floor((lo + hi) / 2) is safe for any array length, but the popular shortcut (lo + hi) >> 1 converts to a 32-bit integer and goes negative:
⌘/Ctrl + Enter
OutputNot run yet

Press Run to see what your code prints, in order.

Runs in this browser, in an isolated frame with no access to this page. console.log, info, warn and error are shown; code runs as a classic script, so use an async function for await.

Test it against something obviously right

Binary search is easy to check: compare it with a linear scan on thousands of small random inputs, including empty arrays, duplicates and targets outside the range.

⌘/Ctrl + Enter
OutputNot run yet

Press Run to see what your code prints, in order.

Runs in this browser, in an isolated frame with no access to this page. console.log, info, warn and error are shown; code runs as a classic script, so use an async function for await.

Beyond arrays

The same halving works on anything monotonic: the first version where a test fails (git bisect), the smallest buffer size that is fast enough, or the square root of a number to a given precision. If you can answer "is the answer at or below x?" with yes or no, and the answers flip from no to yes exactly once, you can binary search it.

2

Check yourself

3 questions. Get them all right to finish this topic.

  1. 1.About how many comparisons does binary search need on a sorted array of one billion elements?
  2. 2.With the half-open range [lo, hi), why must the update be `hi = mid` and not `hi = mid - 1`?
  3. 3.In Java, `int mid = (low + high) / 2` broke for very large arrays. Why?

0 of 3 right so far. Get all three to finish this topic.

Go deeper