Menu
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?
871
A binary search only gives you the position of the value you want, or the position of 1 of them if duplicated. To display all duplicates and indexes, you need to do a secondary search around the position returned by binary search routine.
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.
120
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
