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
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.