Author’s vivid memory of Jon Bentley’s lecture at CMU on writing a binary search for incoming Ph.D. students emphasizes the importance of considering program invariants. To the author’s shock, Bentley’s binary search program from Programming Pearls contained a bug related to large integer values. The bug could cause an ArrayIndexOutOfBoundsException or unpredictable results. Various solutions to the bug are proposed, with emphasis on testing programs thoroughly. The bug could impact other algorithms like mergesort. The lesson learned is the difficulty of writing bug-free code, requiring careful design, testing, and vigilance. A C99 standard clarification is provided to ensure the correctness of the fix. The author stresses the need for humility in programming.
https://research.google/blog/extra-extra-read-all-about-it-nearly-all-binary-searches-and-mergesorts-are-broken/