Введение
Интерполяционный поиск — это алгоритм поиска ключа в массиве, упорядоченном по числовым значениям, присвоенным ключам (ключевым значениям). Впервые он был описан У. В. Петерсоном в 1957 году. Интерполяционный поиск напоминает способ, которым люди ищут имя в телефонном справочнике (ключевое значение, по которому упорядочены записи): на каждом шаге алгоритм вычисляет вероятное местоположение искомого элемента в оставшемся пространстве поиска, основываясь на ключевых значениях на границах этого пространства и значении искомого ключа, как правило, с помощью линейной интерполяции. Затем ключевое значение, найденное в этой предполагаемой позиции, сравнивается с искомым ключом. Если они не равны, то, в зависимости от результата сравнения, пространство поиска сужается до части, расположенной до или после предполагаемой позиции. Этот метод эффективен только в том случае, если вычисления разницы между ключевыми значениями имеют смысл. В отличие от него, двоичный поиск всегда выбирает середину оставшегося пространства поиска, отбрасывая одну из половин в зависимости от сравнения найденного ключа с искомым — для его работы не требуется, чтобы ключи имели числовые значения, достаточно лишь общего порядка между ними. Пространство поиска сужается до части, расположенной до или после предполагаемой позиции. Линейный поиск использует только проверку на равенство, последовательно сравнивая элементы с начала, не учитывая сортировку. В среднем интерполяционный поиск выполняет около log(log(n)) сравнений (при условии равномерного распределения элементов), где n — количество элементов в массиве. В худшем случае (например, при экспоненциальном увеличении числовых значений ключей) количество сравнений может достигать O(n). В интерполяционном последовательном поиске сначала используется интерполяция для нахождения элемента, близкого к искомому, а затем линейный поиск для точного определения его местоположения.
Interpolation search is an algorithm for searching for a key in an array that has been ordered by numerical values assigned to the keys (key values). It was first described by W. W. Peterson in 1957. Interpolation search resembles the method by which people search a telephone directory for a name (the key value by which the book's entries are ordered): in each step the algorithm calculates where in the remaining search space the sought item might be, based on the key values at the bounds of the search space and the value of the sought key, usually via a linear interpolation. The key value actually found at this estimated position is then compared to the key value being sought. If it is not equal, then depending on the comparison, the remaining search space is reduced to the part before or after the estimated position. This method will only work if calculations on the size of differences between key values are sensible. By comparison, binary search always chooses the middle of the remaining search space, discarding one half or the other, depending on the comparison between the key found at the estimated position and the key sought — it does not require numerical values for the keys, just a total order on them. The remaining search space is reduced to the part before or after the estimated position. The linear search uses equality only as it compares elements one by one from the start, ignoring any sorting. On average the interpolation search makes about log(log(n)) comparisons (if the elements are uniformly distributed), where n is the number of elements to be searched. In the worst case (for instance where the numerical values of the keys increase exponentially) it can make up to O(n) comparisons. In interpolation sequential search, interpolation is used to find an item near the one being searched for, then linear search is used to find the exact item.
Выступление
Используя нотацию «большое О», производительность алгоритма интерполяции на наборе данных размером n составляет O(n). Однако, при условии равномерного распределения данных на линейной шкале, используемой для интерполяции, можно показать, что производительность составляет O(log log n). Тем не менее, динамический интерполяционный поиск возможен за время o(log log n) с использованием новой структуры данных. Практическая эффективность интерполяционного поиска зависит от того, перевешивает ли уменьшенное количество проверок сложность вычислений, необходимых для каждой проверки. Он может быть полезен для поиска записи в большом отсортированном файле на диске, где каждая проверка включает в себя обращение к диску и значительно медленнее, чем интерполяционная арифметика. Индексные структуры, такие как B-деревья, также уменьшают количество обращений к диску и чаще используются для индексации данных на диске, отчасти потому, что они могут индексировать различные типы данных и могут обновляться в режиме реального времени. Тем не менее, интерполяционный поиск может быть полезен, когда необходимо искать определенные отсортированные, но неиндексированные наборы данных на диске.
Адаптация к различным наборам данных
Когда ключи сортировки для набора данных — равномерно распределенные числа, линейная интерполяция легко реализуется и позволяет найти индекс, очень близкий к искомому значению. С другой стороны, для телефонного справочника, отсортированного по имени, прямой подход к интерполяционному поиску неприменим. Однако те же общие принципы все равно могут быть использованы: можно оценить положение имени в телефонном справочнике, основываясь на относительной частоте встречаемости букв в именах, и использовать это как точку для поиска. Некоторые реализации интерполяционного поиска могут работать некорректно при наличии последовательности одинаковых значений ключей. Самая простая реализация интерполяционного поиска не обязательно выберет первый (или последний) элемент в такой последовательности.
Поиск на основе книг
Преобразование имен в телефонном справочнике в некий числовой код очевидно не даст чисел с равномерным распределением (за исключением огромных усилий, таких как сортировка имен и присвоение им номеров #1, #2 и т.д.). Более того, хорошо известно, что некоторые имена встречаются гораздо чаще других (Смит, Джонс). Аналогичная ситуация и со словарями, где количество слов, начинающихся с определенных букв, значительно превышает количество слов, начинающихся с других. Некоторые издатели прилагают усилия для подготовки сносок на полях или даже делают вырезы по краю страниц, чтобы обозначить начало каждой буквы, позволяя быстро выполнять сегментированную интерполяцию.