Сравнения
Ещё возможны
Двоичному поиску нужно

  • Искомое
  • Ещё возможны
  • Сравниваются
  • Исключено
  • Найдено

Подробнее об экспоненциальном поиске

Экспоненциальный поиск

Экспоненциальный поиск находит значение в отсортированном списке в два этапа. Сначала он смотрит на места 1, 2, 4, 8, 16 и так далее, каждый раз удваивая, пока значение там не окажется не меньше искомого. Затем он ищет двоичным поиском на отрезке между двумя последними местами. Выберите, что искать, и посмотрите, почему значения у начала находятся всего за несколько сравнений. Нажмите «Пуск», чтобы посмотреть поиск, или «Шаг» и «Назад», чтобы идти по одному шагу. Перетащите ползунок шагов, чтобы перейти в любое место. Пунктирная линия отмечает искомое значение, а затенённая часть — где оно ещё может быть. Экспоненциальному поиску нужен отсортированный список, поэтому неотсортированный список сначала сортируется. Выберите значение, число столбиков или введите свои числа. Когда поле выбрано, стрелки делают шаг, пробел запускает и ставит на паузу, а Home и End переходят к началу и к концу.

Как это работает

  1. Выберите значение для поиска и число столбиков. Или введите свои числа: экспоненциальный поиск сначала их отсортирует.
  2. Нажмите «Пуск» или используйте «Шаг» и «Назад», чтобы двигаться по одному шагу. Перетащите ползунок шагов, чтобы перейти в любое место поиска.
  3. Поищите значение у начала и значение у конца и сравните счётчик с плиткой «Двоичному поиску нужно».

Как работает экспоненциальный поиск

Посмотрите на значение на месте 1. Если оно меньше искомого, посмотрите на место 2, затем 4, 8, 16, каждый раз удваивая. Как только значение окажется не меньше, остановитесь: искомое может лежать только после предыдущего проверенного места и перед этим. Найдите его двоичным поиском на этом отрезке. Если удвоение выходит за конец списка, ищите двоичным поиском от последнего проверенного места до конца.

Быстро у начала, и длина не нужна

Чтобы дойти до искомого на месте i, удвоению нужно около log₂ i проверок, а найденный отрезок содержит меньше i значений, поэтому двоичному поиску нужно ещё около log₂ i. Всего около 2 log₂ i, и это зависит от того, где стоит искомое, а не от длины списка. Значения у начала находятся быстрее, чем обычным двоичным поиском; значения у конца обходятся дороже, примерно до двух раз. Поскольку длина списка не нужна, метод работает и на списках, которые слишком длинны, чтобы их измерить, или не имеют известного конца.

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

Как работает экспоненциальный поиск?

В отсортированном списке он проверяет места 1, 2, 4, 8 и так далее, пока значение там не окажется не меньше искомого. Тогда искомое может лежать только между двумя последними проверенными местами, и двоичный поиск на этом отрезке его находит.

Экспоненциальный поиск быстрее двоичного?

Если искомое близко к началу списка — да: для искомого на месте i нужно около 2 log₂ i сравнений при любой длине списка. Если искомое близко к концу, обычный двоичный поиск быстрее, примерно до двух раз.

Для чего он нужен?

Для поиска в списках неизвестной или неограниченной длины, например в потоке данных или бесконечной последовательности, и для слияния отсортированных серий, где следующее совпадение обычно рядом. Режим галопа в Timsort использует ту же идею удвоения.

Почему он называется экспоненциальным?

Потому что проверяемые места растут экспоненциально: 1, 2, 4, 8, 16, каждое вдвое дальше предыдущего. Его также называют поиском с удвоением или галопирующим поиском.

Мои числа куда-нибудь отправляются?

Нет. Поиск работает в вашем браузере, а последние настройки хранятся в локальном хранилище этого браузера.

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

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

Перейти в редактор