Binary Search Is Simple Until You Try to Implement It Correctly

There is a famous statistic from Jon Bentley's "Programming Pearls": when professional programmers were given the specification for binary search and asked to implement it, only about 10% got it right. Binary search has been known since 1946, and the first correct published implementation did not appear until 1962. Even Java's Arrays.binarySearch had an overflow bug that went undetected for nine years. Binary search is the canonical example of an algorithm that is trivially easy to describe and surprisingly hard to implement correctly. The Algorithm in Plain English Given a sorted array and a target value: Look at the middle element. If it equals the target, you are done. If the target is smaller, repeat on the left half. If the target is larger, repeat on the right half. If the search space is empty, the target is not in the array. That is it. A child can understand the concept. The devil is entirely in the details. The Classic Implementation def binary_search ( arr , target ): low =