What are the pitfalls in implementing binary search?

Question

Binary search is harder to implement than it looks. "Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky…" — Donald Knuth.

Which bugs are most likely to be introduced into a new binary search implementation?

Answer 1

Here are some I can think of:

• Off-by-one errors, when determining the boundary of the next interval
• Handling of duplicate items, if you are suppose to return the first equal item in the array but instead returned a subsequent equal item
• Numerical underflows/overflows when computing indices, with huge arrays
• Recursive vs non-recursive implementation, a design choice you should consider

Are these what you have in mind?