Look up a word in a sorted list by opening to the middle and throwing away half, again and again — twenty steps find one item in a million. Simple enough that almost everyone gets it wrong: the canonical implementation carried a hidden bug for decades. And it runs in real I-13 now, on the new array — where every index is bounds-checked, the exact discipline the famous bug lacked.
THE TECHNIQUE keep the half that could hold it
Compare the target to the middle element; if smaller, search the left half, else the right. The live window (gold = lo/hi, green = mid) shrinks by half each step. live demo
HISTORY & CREDIT the bug that hid in plain sight
“It’s trivial” — and yet the first correct published binary search came twelve years after the first published one. cited
1946 · John Mauchly describes the method in the Moore School lectures; the idea is immediate, the details are not. 1960 · Derrick Henry Lehmer publishes a correct general version — after years of buggy ones in the literature. 1986 · Jon Bentley (Programming Pearls) reports that ~90% of professional programmers he tested could not write a correct binary search in two hours. 2006 · Joshua Bloch blogs “Nearly All Binary Searches and Mergesorts are Broken”: mid = (lo + hi) / 2 overflows for large arrays — a bug that had lived in the JDK for nine years, and in Bentley’s own book.
The simplest useful algorithm is a monument to how hard “simple” is. humbling
RECOMMEND FOR I-13 a no-wall — and the bug’s antidote
Binary search over the new array is pure indexed reads and comparisons. It runs, exactly:
def bs(I a, I lo, I hi, I t) {
if lo >= hi { -> 0 - 1 }
I mid <- (lo + hi - (lo + hi) % 2) / 2
I v <- a[mid]
if v == t { -> mid }
if v < t { -> bs(a, mid + 1, hi, t) }
-> bs(a, lo, mid, t)
}
$ i13 run bsearch.i13
i23 = 5 # found 23 at index 5
i7 = -1 # 7 is absent
Recommend:nothing new — and note the happy accident: the Bloch overflow bug cannot happen in I-13. Indices are f64 (exact to 2⁵³, far past any bounded array), and every access is bounds-checked (out-of-range is a clean E0501, never silent corruption). The language’s refusal of undefined behaviour is exactly the discipline the world’s most famous binary-search bug was missing. Payoff: this is the first dart to run on the bounded array the author just added — the aggregate wall, cleared.