Five searching methods for sorted are provided:

• Linear search,
• Jump search,
• Binary search,
• Interpolation search,
• Introspective search, and
• Distribution search.

The run times of linear and binary searches are O(n) and O(ln(n)), respectively.

The two implementations of jump search run in O(√n) and O(n^1/3) time, respectively.

Interpolation search runs in O(ln(ln(n))) time for uniformly-distributed arrays; however, there are pathological cases which run in O(n) time.

Introspective search corrects the weakness in interpolation search to reduce the worst case to to O(ln(n)) time without affecting the sub-logarithmic search times.

A distribution search can reduce the run time to O(1).