The heuristic for this, FWIW, is to think about reducing the number of things you're messing with (such as a search set) by a factor (usually 2, not always) on

The heuristic for this, FWIW, is to think about reducing the number of things you're messing with (such as a search set) by a factor (usually 2, not always) on every iteration. A binary search is a logarithmic algorithm because you chop off half of the (sorted) search set on every pass. That's all you really need to know about it to identify one (and thus realize you have a sublinear-time algorithm).