Binary Search broken

[tHeFiRsTiDioT]

...Fast forward to 2006. I was shocked to learn that the binary search program that Bentley proved correct and subsequently tested in Chapter 5 of Programming Pearls contains a bug. Once I tell you what the it is, you will understand why it escaped detection for two decades.

This is a snippet from the official google research blog. It seems that even the implementation of binary search in the Sun Java JDk contains a bug. And it lay dormant for 9 yrs. Here is the entire blog -
Official Google Research Blog: Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken

Check out the last paragraph. Eternal vigilance blah blah blah.

Any comments software programmers?

 

[Chaos]

Duh... What he said is trivial . Its a pretty standard bug in many many pieces of code that I've seen. I'm really really surprised that programming pearls had such an obviously blatant mistake. Anyway here is the real code the google fellow is talking about

http://netlib.bell-labs.com/cm/cs/pearls/search.c

 

[superczar]

edit: posted in Wrong thread ...Plz delete post :ashamed:

 

[tHeFiRsTiDioT]

What was probably of more interest to me was the last paragraph....

The fact is that its such a simple piece of code, and yet there are mistakes which lie undiscovered for so long. This is just an example. I bet enough people would have noticed this, but not bothered, because it didnt break their code

 

[deathvirus_me]

Nice find ... never though of it ... "int" ... then again limited by "long int" .. and so on ... coz we always have to round of that value ....

I mainly use hreaded searching and sorting .... i mean thats why we improve our programming capabilities don't we ?? ??? left binary search such a long time ago ... specially when i started java ...

Infact ... there should be many more silly errors like this all around ... just skipping our eyes somehow ....