I'm no mathematician, but I think that if you know something about the probability distribution before searching, then you can be more efficient than blindly using binary search. And if you assume Ballmer is out to get you (i.e. the distribution is not random) then you can use that information to improve the search speed.