The point is that Ballmer is an adversary, and may choose the worst cases for binary search. As I understood, the algorithm in TFA holds against any choice.

As others said, if you don't expect adversary behavior in your data, it should be good enough.