Binary Search Problems? [duplicate]

Question

Possible Duplicate:
What are the pitfalls in implementing binary search?

I was perusing the wikipedia page for Binary Search and stumbled on a quote by Knuth below:

"Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky"

I recall implementing several Binary Searches as part of my Computer Science curriculum, but don't remember it being terribly tricky. However, this article states that 90% of surveyed professionals can't get one working after several hours. I'd like to assume this not because these are terrible programmers, but that there are fringe cases that naive implementations don't account for.

What are the details that Knuth is referring too? What are the common gotchas to be aware of if implementing a Binary Search algorithm?

Note I read that article by Bloch about the Programming Pearls bug(overflow of an int for midpoint). Is there anything else?

Answer 1

Being in Java world in my day job, I remember this. I was pretty surprised when I first read it so this may be one of the things Donald was talking about.