Поиск прыжками

Поиск прыжками — это то, как вы ищете страницу в книге без оглавления: листаете вперёд сразу по куску, поглядывая на номера страниц, а проскочив нужное место, листаете назад последний кусок. В отсортированном списке ему нужно гораздо меньше сравнений, чем при проверке каждого значения.

Отсортированный ряд столбиков, разбитый на блоки: последний столбик каждого пропущенного блока бледный, а блок, где может быть искомое значение, затенён
Отсортированный ряд столбиков, разбитый на блоки: последний столбик каждого пропущенного блока бледный, а блок, где может быть искомое значение, затенён

Идея

В отсортированном списке последнее значение блока показывает, может ли искомое вообще быть в этом блоке: если оно меньше искомого, то и все значения в блоке меньше. Значит, заглядывать внутрь не нужно. Проверяйте по очереди последнее значение каждого блока, пропуская целые блоки, пока одно из них не окажется не меньше искомого. Тогда искомое может быть только в этом блоке: просмотрите его с начала.

Пример

Ищем 23 в списке 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 блоками по 3. Первый блок заканчивается на 8, это меньше, поэтому пропускаем его. Второй блок заканчивается на 23, это не меньше, поэтому 23 может быть только среди 12, 16, 23. Просмотр даёт 12, 16, а затем 23: найдено за 5 сравнений, тогда как линейному поиску нужно 6, а двоичному 3. При поиске 40 концы блоков 8, 23 и 72 приводят к блоку 38, 56, 72; 38 меньше, а 56 уже больше, значит, 40 там нет: снова 5 сравнений.

Почему √n

При блоках по m значений поиск нужного блока занимает не больше примерно n/m сравнений, а его просмотр — не больше m. Редкие длинные прыжки удлиняют просмотр; частые короткие удлиняют прыжки. Сумма n/m + m минимальна, когда обе части равны, то есть при m = √n, и тогда она около 2√n. Для 40 значений это блоки по 6 и не больше 13 сравнений; для миллиона значений — блоки по 1000 и около 2000 сравнений.

Где он уместен

Двоичному поиску нужно меньше сравнений, около log₂ n. Но двоичный поиск прыгает туда и обратно по всему списку, а поиск прыжками движется только вперёд и отступает назад один раз — к началу одного блока. Поэтому он был удобен для данных на ленте или в связной структуре, где возвращаться назад медленно. Ben Shneiderman описал его в 1978 году как jump searching. Та же идея разбиения на √n блоков, которую часто называют корневой декомпозицией, встречается во многих других алгоритмах.

Бен Шнейдерман (слева) с Катрин Плезен на Webshop 2012. Шнейдерман описал поиск прыжками в 1978 году.
Бен Шнейдерман (слева) с Катрин Плезен на Webshop 2012. Шнейдерман описал поиск прыжками в 1978 году.

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

Откройте приложение, выберите значение в поле «Искать» и нажмите «Шаг». Каждый прыжок выделяет последнее значение блока; пропущенные блоки бледнеют, а блок, где может быть искомое, затенён, пока его просматривают. При 40 столбиках смените в поле «Длина прыжка» √n на 2 или 8 и посмотрите, как сдвигается баланс между прыжками и просмотром.

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

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

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

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

Двоичный поиск каждый раз делит оставшуюся часть пополам и требует около log₂ n сравнений, но движется туда и обратно. Поиск прыжками идёт вперёд фиксированными шагами и просматривает один блок, требует около 2√n сравнений и отступает назад лишь один раз.

Можно ли в последнем блоке вместо просмотра использовать двоичный поиск?

Да. Двоичный поиск в блоке сокращает просмотр с m сравнений примерно до log₂ m. Прыжки по-прежнему стоят n/m, поэтому тогда выгоднее более крупные блоки.

Нужен ли поиску прыжками отсортированный список?

Да. Пропускать блок безопасно только потому, что меньшее последнее значение означает, что все значения в блоке меньше. Приложение сначала сортирует неотсортированный список.

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

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

Попробовать поиск прыжками