Binary Search Problems? [duplicate]

问题:

This question already has answers here:

Closed 8 years ago.

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?

回答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.

回答2:

One of the best reference for the tricky point of binary search is Jon Bentley's Programming Pearls.

The whole chapter 4 addresses this problem, which shows many wrong versions of binary search.

e.g. you want to find the first number that is greater than or equal to your query x. Think about the +1 -1 problems therein. How can you prove that your procedure is exactly correct?

Thinks about these problems and you will find that it is not that easy.