I agree with @wohlstad, its premise is based on the principle of removing half the currently valid data from the results. The distribution of the data is irrelevant since the results would have to be sorted before a binary search is performed.