Interactive Math & Science Lessons

← Computing

Binary Search: Four Choices, Sixteen Loops

Pick the four choices in the code: the loop condition, where hi starts, and the two updates. The run beside it shows that loop on a small sorted array one pass at a time, and the verdict tests it on every array up to the length you set and every target, with the first failing case one click away.

Loading interactive simulation...

Lesson

The theory — Binary Search: Four Choices, Sixteen Loops

Binary search finds a value x in a sorted array by keeping a range of indices from lo to hi that must contain x if x is there at all. Each pass reads the middle element, a[mid], and keeps the half on x's side. The range is closed when hi is the last index still in it (lo <= hi, hi starting at n − 1) and half-open when hi is the first index past it (lo < hi, hi starting at n).

What each symbol means

lo, hi
the ends of the range still to search
mid
⌊(lo + hi)/2⌋, the index read on this pass
n
the number of elements, at indices 0 to n − 1
N
the longest array the verdict tests: every n from 0 to N and every target, (N + 1)² cases
Assumes
Different values in the array, a loop that returns as soon as a[mid] equals x, and, in the run and the verdict, integers with no upper limit. The overflow table drops that last assumption and does the arithmetic in 32 bits, as Java does.
Breaks when
With repeated values the two correct loops still return an index that holds x, but not necessarily the first. Finding the first, which a range query on a sorted index needs, takes a loop that does not stop on equality: half-open, hi = mid whenever a[mid] ≥ x, and lo is the answer when the loop ends.

Fourteen of the sixteen loops are wrong, and two elements show it 🖖

Each of the four choices in the code is one a careful programmer makes, and both options of each look reasonable. The table under the results runs all sixteen loops against every array of up to 12 elements and every target, 169 cases, and two pass. Every other loop fails on an array of at most two elements, and thirteen of the fourteen on one element or on the empty array. Set the test to 1 element and three loops survive; at 2 only the two correct ones are left; at 256 not one first failure moves. Those small cases are a complete test rather than a sample, because the loop does nothing with a value except compare it with x. Any sorted array of n different numbers behaves like 1, 3, 5 … with the target in one of its 2n + 1 slots, on an element or in a gap, and the verdict tries every slot. Jon Bentley's Programming Pearls puts the difficulty in two dates: "While the first binary search was published in 1946, the first binary search that works correctly for all values of n did not appear until 1962."

The two nearly right loops each miss at most one target per array 🖖

Press Misses the last. lo < hi with hi = n − 1 stops when lo meets hi, without reading the element they meet on. Every update keeps x inside the range and mid never lands on hi, so the one element the loop can fail to read is the one hi starts on: it finds every element of every array except the last. Press Reads past the end for the mirror image. hi = n with lo <= hi puts a[n] inside the range, and only a target above every element walks lo up to it. Up to 256 elements the two loops get 256 and 257 of the 66,049 cases wrong, and on the 256-element array alone 0.19% of the targets, so a hundred random targets on that array would usually miss both bugs. The empty array catches the second loop on its only case, and an array of one element catches the first. The second loop even gets away with it in JavaScript: a[n] is undefined, both comparisons with it are false, and the loop sets hi = mid − 1 and answers −1, correctly. In Java the same read throws an exception, and in C its behaviour is undefined.

The JDK's correct loop broke past 230 elements 🖖

The JDK's loop is the first row of the table, right in every case the verdict can try, and it is the loop Joshua Bloch wrote for java.util.Arrays. In Java, lo + hi is a 32-bit int, and past 2,147,483,647 it wraps round to a negative number. A bug report filed with Sun on 11 May 2004 searched a 1,100,000,000-byte array for its last element and got ArrayIndexOutOfBoundsException: -1064671149. The overflow table repeats that search with nothing allocated: on step 6, lo + hi is 2,165,624,999, and after the wrap and the shift the midpoint is −1,064,671,149, the number in the report. lo + ((hi − lo) >> 1) gives 1,082,812,499 on the same step. The report's title says the search fails for arrays larger than 1<<30, and that is exact: type 1,073,741,824 and the largest lo + hi is 231 − 2, which fits; one element more and the search overflows on step 31. Bloch's 2006 post on the bug says it lay in wait "for nine years or so", and that Bentley's own version in Programming Pearls, proved correct there, has it too. Bentley's line "sets m to the average of l and u, truncated down to the nearest integer" is true of integers and false of 32-bit ones.

Problem solved in full

  1. Why only two loops are left standing 4 steps

    Press Stuck at lo = mid. The verdict can test arrays up to 256 elements and no longer. Show, for every n, that the half-open loop with lo = mid + 1 always ends, that the same loop with lo = mid sticks whenever hi = lo + 1 and a[lo] < x, and what the same reasoning demands of the closed loop.

    Open this problem in the tool

    1. In the half-open loop the body runs only while lo < hi, and then mid, rounded down, is at least lo and strictly less than hi.

    2. So hi = mid pulls hi down by at least one, and lo = mid + 1 pushes lo up by at least one. Either way hi − lo, which starts at n, falls by at least one each pass, and it cannot go below zero: the loop ends within n passes.

    3. Now take lo = mid. When hi = lo + 1, mid is ⌊(2lo + 1)/2⌋ = lo, so if a[lo] < x the update leaves lo where it was and the next pass is the same pass. The preset reaches it at lo = 6, hi = 7, with a[6] = 13 and x = 14.

    4. The closed loop runs while lo <= hi, so lo = hi is allowed, and then mid = lo = hi: an update to mid changes nothing, so both updates must step past mid, which they can afford because a[mid] has just been read. The half-open range already excludes hi, so there hi = mid drops the element just read and everything above it, all ruled out by a[mid] > x, while hi = mid − 1 would also drop a[mid − 1], which may be x.

    Answer

    Every pass must shrink the range, must throw away only indices that cannot hold x, and the range must start as the whole array. For lo <= hi that means hi = n − 1, hi = mid − 1 and lo = mid + 1; for lo < hi, hi = n, hi = mid and lo = mid + 1. The verdict confirms the two survivors up to 256 elements, and the argument holds for every n, which is what no test can do. In 32-bit arithmetic it needs one more premise, that lo + hi fits, and the third insight is what happened without it.

Learning path

Why an algorithm is correct

References (2)

· Reviewed against published sources. Corrections welcome.