Encyclopedia > Interpolation search

  Article Content

Interpolation search

Interpolation search parallels how humans search through a telephone book. Instead of comparing against every item like the linear search, it attempts to find the item by approximating how far the item is likely to be from the current position. This differs from the binary search, in that the binary search always divides the search space[?] in half. The interpolation search makes fewer than O(log(log(N)) comparisons, where N is the number of elements to be searched, however in reality it is often no faster than binary search due to the complexity of the arithmetic calculations of approximating the indices.

The interpolation search, like the binary search, requires that the values be sorted and randomly accessible. It works by making the assumption that values are uniformly distributed, and thus uses the end values to compute an index.

External Links:

All Wikipedia text is available under the terms of the GNU Free Documentation License

  Search Encyclopedia

Search over one million articles, find something about almost anything!
  Featured Article

... - Wikipedia <<Up     Contents Autocracy Autocracy is a form of government which resides in the absolute power of a single individual. The term ...

This page was created in 23.7 ms