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