Интерполирующий поиск

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск


Интерполирующий поиск основан на принципе поиска в телефонной книге или, например, в словаре. Вместо сравнения каждого элемента с искомым как при линейном поиске, данный алгоритм производит предсказание местонахождения элемента: поиск происходит подобно двоичному поиску, но вместо деления области поиска на две части, интерполирующий поиск производит оценку новой области поиска по расстоянию между ключом и текущим значением элемента. Другими словами, бинарный поиск учитывает лишь знак разности между ключом и текущим значением, а интерполирующий ещё учитывает и модуль этой разности и по данному значению производит предсказание позиции следующего элемента для проверки. В среднем, интерполирующий поиск производит log(log(N)) операций, где N есть число элементов, среди которых производится поиск. Число необходимых операций зависит от равномерности распределения значений среди элементов. В плохом случае (например, когда значения элементов экспоненциально возрастают) интерполяционный поиск может потребовать до O(N) операций.

На практике, интерполяционный поиск часто быстрее бинарного, так как с вычислительной стороны их отличают лишь применяемые арифметические операции: интерполирование — в интерполирующем поиске и деление на два — в двоичном, а скорость их вычисления отличается незначительно, с другой стороны интерполирующий поиск использует такое принципиальное свойство данных, как однородность распределения значений. Ключом может быть не только номер, число, но и, например, текстовая строка, тогда становится понятна аналогия с телефонной книгой: если мы ищем имя в телефонной книге, начинающееся на «А», следовательно нужно искать его в начале, но никак не в середине. В принципе, ключом может быть всё что угодно, так как те же строки, например, запросто кодируются посимвольно, в простейшем случае символ можно закодировать значением от 1 до 33 (только русские символы) или, например, от 1 до 26 (только латинский алфавит) и т. д.

Интерполяция может производиться на основе функции, аппроксимирующей распределение значений, либо набора кривых, выполняющих аппроксимацию на отдельных участках. В этом случае поиск может завершиться за несколько проверок. Преимущества этого метода состоят в уменьшении запросов на чтение медленной памяти (такой как, например, жесткий диск), если запросы происходят часто.

Часто, анализ и построение аппроксимирующих кривых не требуется, показательный случай здесь — когда все элементы отсортированы по возрастанию. В таком списке, минимальное значение будет по индексу 1, а максимальное по индексу N. В этом случае аппроксимирующую кривую можно принять за прямую и применять линейную интерполяцию.

Следующий пример на Java показывает простейшую реализацию интерполирующего поиска. На каждой стадии алгоритм рассчитывает позицию для следующей проверки, как при двоичном поиске, переносит верхнюю или нижнюю границу, определяя тем самым новую область поиска, содержащую искомое значение.

public int interpolationSearch(int[] sortedArray, int toFind){
 // Возвращает индекс элемента со значением toFind или -1, если такого элемента не существует
   int mid;
   int low = 0;
   int high = sortedArray.length - 1;

   while (sortedArray[low] < toFind && sortedArray[high] > toFind) {
       mid = low + ((toFind - sortedArray[low]) * (high - low)) / (sortedArray[high] - sortedArray[low]);

       if (sortedArray[mid] < toFind)
           low = mid + 1;
       else if (sortedArray[mid] > toFind)
           high = mid - 1;
       else
           return mid;
   }

   if (sortedArray[low] == toFind)
           return low;
   else if (sortedArray[high] == toFind)
           return high;
   else
           return -1; // Not found
}


См. также[править | править исходный текст]

Ссылки[править | править исходный текст]

Литература[править | править исходный текст]

  • Ананий В. Левитин Глава 5. Метод уменьшения размера задачи: Интерполяционный поиск // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Algorithms. — М.: «Вильямс», 2006. — С. 240-242. — ISBN 0-201-74395-7
  • Роберт Седжвик Фундаментальные алгоритмы на C. Анализ/Структуры данных/Сортировка/Поиск = Algorithms in C. Fundamentals/Data Structures/Sorting/Searching. — СПб.: ДиаСофтЮП, 2003. — С. 672. — ISBN 5-93772-081-4