Binary Search implementation issues

When Jon Bentley assigned binary search as a problem in a course for professional programmers, he found that ninety percent failed to provide a correct solution after several hours of working on it,[44] and another study published in 1988 shows that accurate code for it is only found in five out of twenty textbooks.^[45] Furthermore, Bentley's own implementation of binary search, published in his 1986 book Programming Pearls, contained an overflow error that remained undetected for over twenty years. The Java programming language library implementation of binary search had the same overflow bug for more than nine years.^[46]

https://en.wikipedia.org/wiki/Binary_search_algorithm#Implementation_

>>5
You have a tool, it's in your skull.

>>2
...but apparently most people don't make use of this tool.

>>6
Testing doesn't work when you don't even know what to test.

The underlying problem here is that people don't know how to use induction and handle the four cases in total: even-length array, not found; even-length array, found; odd-length array, not found; odd-length array, found.

Binary search sounds deceptively simple: cut the array into two halves, look at the "middle" element and continue with either half if it's not found, until you get down to 1 element. People execute this "algorithm" IRL without realising one key mistake in that description: there is no "middle" element if the length is even, and they're actually looking at an element in either the lower or upper half.

As for the overflow "bug"? It only happens with extremely large arrays. Maybe it was known that it would overflow, but was not a problem because searching an array of 2G elements binarily is just not something done often or even the best way to solve the problem. With 64-bit, the overflow becomes expoentially harder and so I would not consider it a "bug" at all, just an implementation limitation. No one is creating, much less searching arrays of 2^63 elements binarily.