The canonical DecreaseByConstantFactor algorithm. Given a sorted array, find an element by looking at A[n/2]. If A[n/2] equals the target, we are done. Otherwise continue searching in A[1..n/2-1] or A[n/2+1..n].

The recurrence is

- T(n) = T(n/2) + Theta(1)

which has solution T(n) = Theta(lg n).

InterpolationSearch is faster on very large inputs for some input distributions.

BinarySearchTrees are BinaryTrees organized to permit binary search.