Searching

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(n1/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).