"Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky…" — Professor Donald Knuth
When Jon Bentley assigned it as a problem in a course for professional programmers, he found that an astounding ninety percent failed to code a binary search correctly after several hours of working on it, and another study shows that accurate code for it is only found in five out of twenty textbooks (Kruse, 1999). Furthermore, Bentley's own implementation of binary search, published in his 1986 book Programming Pearls, contains an error that remained undetected for over twenty years.
The error wikipedia is talking about is an integer overflow, so it's not the algorithm that's faulty, it's that particular implementation ... and that's hardly something to reject a potential candidate about.
I do want to see a candidate speak about its complexity (demonstrate it at least intuitively), and about the impact that the partitioning function has.
But these are things any CS college student in his second year should know about (otherwise they've wasted their time in college, and frankly I haven't seen many of those).
I'd really wish we'd stop with the "mine is bigger than yours attitude" ... there are lots of good developers out there. They are just more specialized in other domains, and finding the right match is indeed hard ... but the faulty interviews we are so accustomed with are to be blamed.
The overflow error is certainly not a reason to dismiss a candidate. The excerpt from the Wikipedia article doesn't imply that everyone had the same error.
Also, the page provided by sanj contains a recount by a Google employee where he and most of his fellow CS Ph.D. students at CMU were unable to provide a correct implementation of binary search.
Sometimes smart people make dumb mistakes, especially when rushed or stressed.
The funny thing is, the implementation isn't faulty either. Not on any real machine, at least. You don't have enough address space to hold an array large enough to trigger the overflow.
In Java for example, an "int" is 32 bits, even on 64 bits machines/VMs ... where the address space can reach 16.3 million terabytes.
So this little bug can byte, but only if you're manipulating large datasets in memory. And then it's easily discoverable, on top of managed languages anyway (since the index used on an array can't be negative).
No rule says that arrays must be completely loaded on RAM; even more so in Google, where they probably have to spread them over thousands of machines. No excuse, sorry.
Comments
Excerpt from binary search article on Wikipedia:
"Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky…" — Professor Donald Knuth
When Jon Bentley assigned it as a problem in a course for professional programmers, he found that an astounding ninety percent failed to code a binary search correctly after several hours of working on it, and another study shows that accurate code for it is only found in five out of twenty textbooks (Kruse, 1999). Furthermore, Bentley's own implementation of binary search, published in his 1986 book Programming Pearls, contains an error that remained undetected for over twenty years.
http://en.wikipedia.org/wiki/Binary_search_algorithm#The_alg...
The error wikipedia is talking about is an integer overflow, so it's not the algorithm that's faulty, it's that particular implementation ... and that's hardly something to reject a potential candidate about.
I do want to see a candidate speak about its complexity (demonstrate it at least intuitively), and about the impact that the partitioning function has.
But these are things any CS college student in his second year should know about (otherwise they've wasted their time in college, and frankly I haven't seen many of those).
I'd really wish we'd stop with the "mine is bigger than yours attitude" ... there are lots of good developers out there. They are just more specialized in other domains, and finding the right match is indeed hard ... but the faulty interviews we are so accustomed with are to be blamed.
The overflow error is certainly not a reason to dismiss a candidate. The excerpt from the Wikipedia article doesn't imply that everyone had the same error.
Also, the page provided by sanj contains a recount by a Google employee where he and most of his fellow CS Ph.D. students at CMU were unable to provide a correct implementation of binary search.
Sometimes smart people make dumb mistakes, especially when rushed or stressed.
The funny thing is, the implementation isn't faulty either. Not on any real machine, at least. You don't have enough address space to hold an array large enough to trigger the overflow.
Well, yes and no.
In Java for example, an "int" is 32 bits, even on 64 bits machines/VMs ... where the address space can reach 16.3 million terabytes.
So this little bug can byte, but only if you're manipulating large datasets in memory. And then it's easily discoverable, on top of managed languages anyway (since the index used on an array can't be negative).
Well, if you're using int where you mean size_t, that's your bug -- not the binary search.
No rule says that arrays must be completely loaded on RAM; even more so in Google, where they probably have to spread them over thousands of machines. No excuse, sorry.