Skip to content

SYSTEM Cited by 1 source

Programming Pearls (Jon Bentley, 1986 / 2000)

Definition

Programming Pearls is a 1986 algorithms book (Addison-Wesley; 2nd edition 2000) by Jon Bentley, derived from his "Programming Pearls" column in Communications of the ACM. Chapters pose short, self-contained algorithmic puzzles — binary search, sorting, selection, data-structure design — and treat each as a case study in careful program construction: problem definition, invariant identification, stepwise refinement, proof, and measurement.

Wiki relevance

The book is a wiki entity because its Chapter 5 binary search is the canonical "proved-correct-but-wrong" algorithmic bug in Joshua Bloch's 2006 post (Source: sources/2025-01-11-google-nearly-all-binary-searches-and-mergesorts-are-broken-2006). Bentley's explicit invariant — "sets m to the average of l and u, truncated down to the nearest integer" — is true in the mathematical integers and false in the fixed-width int machine representation. The bug wasn't in the algorithm; it was in the substrate gap between Bentley's stated invariant and the language's arithmetic. See concepts/integer-overflow.

The wiki mnemonic — Bentley's lesson is "consider the invariants"; Bentley's code is the counterexample to not checking them against the substrate — is the origin point for patterns/invariant-driven-programming.

Relevance beyond the binary-search bug

  • The book's central method — "carefully consider the invariants in your programs" — is the wiki's invariant-driven-programming pattern in seed form. Bloch's post opens with the CMU Algorithms lecture in which Bentley taught this to Ph.D. students by dissecting their broken binary searches.
  • The book is the upstream source for the (low + high) / 2 idiom that propagated into JDK Arrays.binarySearch (systems/openjdk-arrays-binarysearch) and into countless other codebases — the vector by which one arithmetic bug touched an entire language ecosystem.
  • Bentley's 1st-edition claim: "the first binary search that works correctly for all values of n did not appear until 1962" — quoted verbatim in Bloch's post as the note that very few correct versions have ever been published, at least in mainstream programming languages.

Seen in

Last updated · 200 distilled / 1,178 read