PineWikiThe 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.