- Искомое
- Ещё возможны
- Сравниваются
- Исключено
- Найдено
Интерполяционный поиск
Интерполяционный поиск ищет значение в отсортированном списке так, как вы открываете телефонный справочник: фамилию на Т вы ищете ближе к концу, а не в середине. Он оценивает место искомого по значениям на обоих концах оставшейся части. Выберите значение и распределение значений, пройдите пробы по шагам и посмотрите, когда оценка обгоняет двоичный поиск, а когда нет. Нажмите «Пуск», чтобы посмотреть поиск, или «Шаг» и «Назад», чтобы идти по одному шагу. Перетащите ползунок шагов, чтобы перейти в любое место. Пунктирная линия отмечает искомое значение, а затенённая часть — где оно ещё может быть. Интерполяционному поиску нужен отсортированный список, поэтому неотсортированный список сначала сортируется. Выберите значение, распределение значений, число столбиков или введите свои числа. Когда поле выбрано, стрелки делают шаг, пробел запускает и ставит на паузу, а Home и End переходят к началу и к концу.
Как это работает
- Выберите искомое значение, распределение значений и число столбиков. Или введите свои числа: интерполяционный поиск сначала их отсортирует.
- Нажмите «Пуск» или используйте «Шаг» и «Назад», чтобы двигаться по одному шагу. Перетащите ползунок шагов, чтобы перейти в любое место поиска.
- Переключайте «Распределение» между вариантами «Равномерное», «Случайные пропуски» и «Перекошенное» и сравнивайте «Пробы» с «Двоичному поиску нужно».
Как работает интерполяционный поиск
Посмотрите на первое и последнее значение той части отсортированного списка, где ещё может быть искомое. Если искомое лежит, скажем, на 40% пути от первого значения к последнему, проверьте место на 40% длины. Если там искомое, поиск закончен. Если значение там меньше, остаются только места после него; если больше — только места перед ним. Снова сделайте оценку в оставшейся части. Если искомое меньше первого значения или больше последнего, его нет в списке.
Когда оценка работает
Если значения распределены равномерно, например 10, 20, 30 и так далее, первая оценка попадает в искомое или очень близко к нему, и поиску в среднем нужно около log₂(log₂ n) проб: около 5 для миллиарда значений против 30 у двоичного поиска. Если значения сбиваются в кучу, например 1, 2, 3, 4, 1000, оценки раз за разом попадают не туда, и каждая проба может убрать лишь одно значение, так что в худшем случае нужно n проб. Двоичному поиску никогда не нужно больше примерно log₂ n.
Часто задаваемые вопросы
Как работает интерполяционный поиск?
В отсортированном списке он оценивает, где должно быть искомое, по первому и последнему значению оставшейся части, проверяет это место и оставляет только часть с нужной стороны. Это как двоичный поиск, но с более умной догадкой, чем середина.
Интерполяционный поиск быстрее двоичного?
На равномерно распределённых значениях да: в среднем около log₂(log₂ n) проб вместо примерно log₂ n. На неравномерно распределённых значениях он может быть гораздо медленнее, вплоть до n проб, тогда как двоичному поиску никогда не нужно больше примерно log₂ n.
Почему он может быть медленным?
Потому что оценка предполагает, что значения растут равномерно. Если большинство значений маленькие, а несколько огромные, оценка для маленького искомого снова и снова попадает близко к началу и каждый раз убирает лишь одно-два значения.
Где используется интерполяционный поиск?
Там, где ключи распределены почти равномерно, а пробы дороги, например при поиске записей на диске по числовому ID или хешу. Многие системы сочетают его с двоичным поиском, чтобы сохранить хороший худший случай.
Мои числа куда-то отправляются?
Нет. Поиск работает в вашем браузере, а последние настройки хранятся в локальном хранилище этого браузера.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Перейти в редактор