Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Not likely, but possible. This reminds me of the bug that was found in the binary search algorithm a few years ago, IIRC, in Java. The interesting thing is that binary search is probably one of the earliest-invented algorithms. Yet, in the book Writing Efficient Programs by Jon Bentley (which I mentioned in a recent HN comment), he says that in a class he taught to several industrial programmers with many years of experience, some had bugs in their implementations of binary search that he set them as an exercise. Not sure but I think I remember reading in the article about the Java binary search issue, that even his algorithm had the bug that was found in the Java version. Why it was not found earlier is (maybe) because it only occurred with an extremely large array, IIRC. Don't have a link right now, but it can probably be found by searching for the right phrase.


Just did a google search, and it even partially auto-completed this search for me:

bug in java binary search

and showed a related search in the drop-down, 'programming pearls ...', a book by Jon Bentley, which seems to confirm what I said above (though I saw it in his other book, "Efficient Programs", IIRC - he might have mentioned the same issue in the Programming Pearls book too).

Edit: and the Wikipedia article confirms it too:

https://en.wikipedia.org/wiki/Binary_search_algorithm#Implem...



Yes, that's it, by the desc. and dates shown.



Yes, thanks, that closely describes the assignment I read that he gave.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: