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

Идея

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

Алгоритм

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

Пусть [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].

Псевдокод

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
}

Время работы

Асимптотически интерполяционный поиск превосходит по своим характеристикам бинарный. Если ключи распределены случайным образом, то за один шаг алгоритм уменьшает количество проверяемых элементов с [math] n [/math] до [math] \sqrt n [/math]. То есть, после [math]k[/math]-ого шага количество проверяемых элементов уменьшается до [math]n^{\frac{1}{2^k}}[/math]. Значит, остаётся проверить только 2 элемента (и закончить на этом поиск), когда [math]\frac{1}{2^k} = log_{n}2 = \frac{1}{log_{2}n} [/math]. Из этого вытекает, что количество шагов, а значит, и время работы составляет [math]O(\log \log n)[/math].

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

Литература

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