10

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?

Community
  • 1
  • 1
nsfyn55
  • 14,875
  • 8
  • 50
  • 77
  • 1
    looked like hell for a duplicate - I promise. Tried problems, issues, but guess the money term was 'pitfalls' – nsfyn55 Jun 16 '11 at 13:01
  • 1
    I've just posted [a long answer at the duplicate question](http://stackoverflow.com/questions/504335/what-are-the-pitfalls-in-implementing-binary-search/6393352#6393352). But no answer is long enough to cover all the ways binary search can be wrong. :-) – ShreevatsaR Jun 18 '11 at 01:50
  • [This is one article](http://www.paultaylor.eu/algorithms/binary.html) which explains a few different ways of implementing binary search, and has a couple of exercises to teach how behaviour changes once you change the bounds, comparisons etc. – nawfal Jun 19 '14 at 10:02

2 Answers2

3

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.

omermuhammed
  • 7,365
  • 4
  • 27
  • 40
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.

Yin Zhu
  • 16,980
  • 13
  • 75
  • 117