Интерполяционный поиск: Умнее бинарного

Цели урока

• Понять идею интерполяции в поиске
• Реализовать интерполяционный поиск
• Знать когда он лучше/хуже бинарного

Предварительные знания

• Бинарный поиск

• Бинарный поиск

Когда вы ищете слово в словаре, вы не открываете его посередине. Вы прикидываете, где примерно должно быть слово. Интерполяционный поиск делает то же самое - и иногда побеждает бинарный в 6 раз!

• Поиск по timestamp в time-series базах данных
• Индексы с числовыми ключами
• Научные данные (измерения с равным шагом)

Уильям Питерсон и интерполяционный поиск в IBM

Интерполяционный поиск описал Уильям Уэсли Питерсон в 1957 году в статье Addressing for Random-Access Storage в IBM Journal of Research and Development. Питерсон занимался хранением данных на дисках и барабанах, где время доступа к произвольной записи было дорогим, и искал способ угадывать положение ключа точнее, чем простое деление пополам. Сама идея пришла из счётных книг и таблиц: когда значения распределены равномерно, по самому ключу можно прикинуть, где он лежит, как при поиске слова в словаре. Питерсон показал, что для равномерно распределённых данных такой поиск делает в среднем порядка log log n обращений вместо log n у бинарного. Позже теоретики уточнили анализ: Yao и Yao в 1976 году доказали, что O(log log n) это асимптотически оптимальная граница для поиска в равномерных данных. Но у метода есть жёсткая оговорка: на неравномерном или враждебном распределении интерполяционный поиск деградирует до O(n), хуже надёжного бинарного. Поэтому в реальных библиотеках он встречается редко, зато его идея напрямую возродилась в learned indexes 2018 года, где позицию ключа предсказывает обученная модель.

Идея: угадываем позицию

**Представьте телефонный справочник:** ищете 'Павлов'. Вы открываете примерно на 2/3 книги, а не посередине. Почему? Потому что 'П' ближе к концу алфавита.

**Интерполяционный поиск** делает то же самое - угадывает позицию по значению:

**Формула:** предполагаем линейное распределение и вычисляем, где должен быть target.

Реализация

**Важные проверки:** `arr[left] <= target <= arr[right]` и деление на 0 при `arr[left] == arr[right]`.

Анализ сложности

**Почему O(log log n)?**

**Worst case O(n):** если данные распределены неравномерно (например, [1, 2, 3, 1000000]), интерполяция ошибается, и каждый шаг сдвигается на 1.

Когда использовать

**Используйте интерполяционный поиск когда:**

• Данные **равномерно распределены** (или близко к этому)
• Вы **уверены в распределении** (нет выбросов)
• n очень большое (разница log log n vs log n заметна)
• Сравнение дешёвое, но арифметика не проблема

**Используйте бинарный поиск когда:**

• Распределение **неизвестно или неравномерное**
• Есть **выбросы** (outliers)
• Важна **гарантированная сложность** O(log n)
• Код должен быть **простым и надёжным**

**На практике** бинарный поиск используют в 99% случаев. Интерполяционный - экзотика для специфичных задач с большими равномерными данными.

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

• Угадывает позицию по значению
• O(log log n) для равномерных данных
• O(n) для неравномерных - хуже бинарного!
• Используйте только если уверены в распределении
• На практике бинарный надёжнее

Связанные темы

Интерполяционный поиск - пример адаптивного алгоритма.

• Бинарный поиск — Более надёжная альтернатива
• Exponential Search — Для unbounded arrays

Связанные уроки

• alg-10-binary-search — Интерполяционный поиск заменяет фиксированную середину умной формулой - O(log log n) вместо O(log n) при равномерных данных
• alg-09-linear-search — На неравномерных данных интерполяционный деградирует до O(n) - хуже бинарного, лучше понимать все три алгоритма
• ds-11-bst — B-tree индексы в БД используют похожую идею: зная распределение ключей, можно предсказывать позицию
• stat-09-regression