- Искомое
- Текущий блок
- Сравниваются
- Исключено
- Найдено
Поиск прыжками
Поиск прыжками находится между линейным и двоичным поиском. Он идёт по отсортированному списку прыжками по m мест и проверяет только последнее значение каждого блока, пока не дойдёт до блока, последнее значение которого не меньше искомого. Затем он просматривает этот блок с начала. Выберите значение и длину прыжка и посмотрите, сколько сравнений уходит на прыжки и на просмотр. Нажмите «Пуск», чтобы посмотреть поиск, или «Шаг» и «Назад», чтобы идти по одному сравнению. Перетащите ползунок шагов, чтобы перейти в любое место. Пунктирная линия отмечает искомое значение, а затенённая часть — текущий блок. Поиску прыжками нужен отсортированный список, поэтому неотсортированный список сначала сортируется. Выберите значение, длину прыжка, число столбиков или введите свои числа. Когда поле выбрано, стрелки делают шаг, пробел запускает и ставит на паузу, а Home и End переходят к началу и к концу.
Как это работает
- Выберите искомое значение, длину прыжка и число столбиков. Или введите свои числа: поиск прыжками сначала их отсортирует.
- Нажмите «Пуск» или используйте «Шаг» и «Назад», чтобы идти по одному сравнению. Перетащите ползунок шагов, чтобы перейти в любое место поиска.
- Попробуйте длину прыжка 2 и 8 на 40 столбиках и сравните число сравнений с √n.
Как работает поиск прыжками
Разбейте отсортированный список на блоки по m значений. Посмотрите на последнее значение первого блока. Если оно меньше искомого, искомого нигде в этом блоке быть не может, поэтому прыгните в конец следующего блока и посмотрите снова. Как только последнее значение блока окажется не меньше, искомое может быть только в этом блоке: вернитесь к его началу и проверяйте значения по одному, пока не найдёте искомое или не пройдёте его.
Как выбрать длину прыжка
При n значениях прыжки занимают до n/m сравнений, а просмотр — до m. Короткие прыжки делают просмотр коротким, но прыжков много; длинные прыжки — наоборот. Сумма n/m + m минимальна при m = √n, что даёт около 2√n сравнений: не больше 13 для 40 значений против 40 у линейного поиска и 6 у двоичного. Поиск прыжками никогда не возвращается больше чем на один блок, и это помогает, когда двигаться по данным назад медленно.
Часто задаваемые вопросы
Как работает поиск прыжками?
В отсортированном списке он прыгает вперёд шагами по m мест и проверяет последнее значение каждого блока. Когда это значение уже не меньше искомого, искомое может быть только в этом блоке, и он просматривает его с начала.
Какая длина прыжка лучше всего?
√n с округлением. Прыжки стоят до n/m сравнений, просмотр — до m, и их сумма минимальна, когда обе части равны, то есть при m = √n. В худшем случае это около 2√n сравнений.
Поиск прыжками быстрее двоичного поиска?
Нет, двоичному поиску нужно меньше сравнений: около log₂ n против около 2√n. Но поиск прыжками может выиграть, когда возвращаться по данным назад дорого, потому что он отступает назад лишь один раз — к началу одного блока.
Какое совпадение он находит, если значения повторяются?
Первое. Каждый пропущенный блок заканчивается значением меньше искомого, поэтому ни в одном более раннем блоке совпадения быть не может, а просмотр начинается с начала блока.
Мои числа куда-нибудь отправляются?
Нет. Поиск выполняется в вашем браузере, а последние настройки хранятся в локальном хранилище этого браузера.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Перейти в редактор