As you point out, the exact properties that make binary search algorithmically fast can slow it down on real computer hardware. Branch predictors like low entr

As you point out, the exact properties that make binary search algorithmically fast can slow it down on real computer hardware. Branch predictors like low entropy (unsurprising) branches, but binary search is algorithmically fast because it maximizes the entropy (information gained) from the few branch checks that it does make.