Интерполяционный поиск

Идея

Рассмотрим задачу: найти слово в словаре. Если оно начинается на букву "А", то никто не будет искать его в середине, а откроет словарь ближе к началу. В чем разница между алгоритмом человека и другими? Отличие заключается в том, что алгоритмы вроде двоичного не делают различий между "немного больше" и "существенно больше".

Алгоритм

Нахождение разделительного элемента

Пусть [math] a [/math] - отсортированный массив чисел из [math] n [/math] чисел, [math] x [/math] - значение, которое нужно найти. Если известно, что [math] x [/math] лежит между [math] a_l [/math] и [math] a_r [/math], то следующая проверка выполняется примерно на расстоянии [math] \frac{x - a_l}{a_r - a_l} [/math] от [math] l [/math].

Время работы

При условии, что значения элементов близки к арифметической прогрессии, за один шаг алгоритм уменьшает количество проверяемых элементов с [math] n [/math] до [math] \sqrt n [/math].
Поэтому среднее время работы алгоритма: [math] O(\log \log n) [/math].
При "плохих" исходных данных (например, при экспоненциальном возрастании элементов) время работы может ухудшиться до [math] O(n) [/math].

Реализация

Приведем код функции [math] \mathrm{interpolation\_search(a, n, x)} [/math] на языке C++.

int interpolation_search(double* a, int n, double x)
{
  int l = 0;
  int r = n - 1;
  int m;

  while (a[l] <= x && x <= a[r])
  {
    m = l + (x - a[l]) / (a[r] - a[l]) * (r - l);

    if (a[m] == x)
      return m;
    if (a[m] < x)
      l = m + 1;
    else
      r = m - 1;
  }

  if (a[l] == x)
    return l;
  else
    return -1; // not found
}

Полезные ссылки

Д.Э. Кнут: Искусство программирования (том 3)
Wikipedia: Interpolation search