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

Когда вы ищете «Taylor» в телефонном справочнике, вы не открываете его посередине: вы открываете его ближе к концу, потому что T стоит в алфавите поздно. Интерполяционный поиск делает то же самое с числами. Он угадывает, где должно быть искомое, по тому, насколько оно велико, и на равномерно распределённых данных эта догадка на удивление хороша.

Отсортированный ряд столбиков с линией от первого до последнего столбика и проба там, где высота искомого пересекает эту линию
Отсортированный ряд столбиков с линией от первого до последнего столбика и проба там, где высота искомого пересекает эту линию

Идея

Двоичный поиск всегда проверяет середину, что бы он ни искал. Интерполяционный поиск использует значения. Если оставшаяся часть списка идёт от 10 до 100, а искомое равно 70, то оно лежит на двух третях пути от первого значения к последнему, поэтому проба делается на двух третях длины. В виде формулы проба находится в месте lo + (target − a[lo]) / (a[hi] − a[lo]) × (hi − lo). После пробы остаётся часть с нужной стороны, точно как в двоичном поиске, и оценка повторяется.

Два примера

В списке 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 поиск 70 сразу проверяет место 7: найдено за 1 пробу, а двоичному поиску нужно 4. Теперь возьмите 1, 2, 3, 4, 5, 6, 7, 8, 9, 999 и ищите 9. Из-за 999 каждая оценка попадает близко к началу: поиск проверяет 1, 2, 3 и так далее, по одному месту, и ему нужно 9 проб, а двоичному поиску — 3.

Насколько он быстр

Когда значения распределены равномерно или взяты случайно из равномерного распределения, каждая проба сокращает оставшуюся часть примерно с n до примерно √n. Это даёт в среднем около log₂(log₂ n) проб: около 5 даже для миллиарда значений против 30 у двоичного поиска. Когда значения распределены очень неравномерно, проба может убрать всего одно значение, и в худшем случае нужно n проб — так же плохо, как у линейного поиска. Каждая проба ещё и стоит деления, поэтому на практике он окупается в основном тогда, когда пробы дороги, например при чтении с диска.

История и варианты

W. W. Peterson описал интерполяционный поиск в 1957 году для поиска записей в памяти с произвольным доступом. Среднее log log n для равномерно распределённых ключей доказали в 1978 году Perl, Itai и Avni. Практические версии защищаются от плохих данных, подмешивая двоичные шаги, например интерполяционно-последовательный или интерполяционно-двоичный поиск, чтобы худший случай оставался близким к log n.

Попробуйте сами

Откройте приложение, выберите значение в поле «Искать» и нажмите «Шаг». Каждая проба сообщает, насколько далеко искомое лежит между двумя крайними значениями и на какое место это указывает. Переключите «Распределение» на «Равномерное», и большинство поисков закончится за одну пробу; переключите на «Перекошенное», и пробы поползут вдоль начала списка. Последняя плитка показывает, сколько шагов понадобилось бы двоичному поиску для того же значения.

Часто задаваемые вопросы

Какова временная сложность интерполяционного поиска?

O(log log n) в среднем для равномерно распределённых значений и O(n) в худшем случае. Ему нужны O(1) дополнительной памяти и отсортированный список.

Чем интерполяционный поиск отличается от двоичного?

Двоичный поиск всегда проверяет середину оставшейся части. Интерполяционный поиск проверяет место, где должно быть искомое, судя по значениям на обоих концах. Это намного лучше на равномерно распределённых значениях и может быть намного хуже на перекошенных.

Какие данные подходят для интерполяционного поиска?

Отсортированные числовые ключи, распределённые довольно равномерно: последовательные ID с небольшим числом пропусков, метки времени регулярных событий или хешированные ключи. Он подходит для данных, где проба дорога, а немного арифметики дёшево.

Зачем в приложении разные распределения?

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

Готовы попробовать?

Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

Попробовать интерполяционный поиск