Simple binary search algorithm broken?

I seems that Google labs have found that nearly all established simple binary search algorithms are broken. Sometimes being bigger IS better 🙂