Интерполяционный поиск
Интерполяционный поиск (интерполирующий поиск) основан на принципе поиска в телефонной книге или, например, в словаре. Вместо сравнения каждого элемента с искомым, как при линейном поиске, данный алгоритм производит предсказание местонахождения элемента: поиск происходит подобно двоичному поиску, но вместо деления области поиска на две части, интерполирующий поиск производит оценку новой области поиска по расстоянию между ключом и текущим значением элемента. Другими словами, бинарный поиск учитывает лишь знак разности между ключом и текущим значением, а интерполирующий ещё учитывает и модуль этой разности и по данному значению производит предсказание позиции следующего элемента для проверки. В среднем интерполирующий поиск производит 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) {
if (sortedArray[high] == sortedArray[low]) // Защита от деления на 0
break;
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;
if (sortedArray[high] == toFind)
return high;
return -1; // Not found
}
