Jump Search

Как и бинарный поиск, поиск с переходом(прыжком) выполним только для отсортированных массивов. Основная идея состоит в том, чтобы проверять меньшее количество элементов, перескакивая вперед на фиксированное количество шагов, пропуская их.

Рассмотрим массив - 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, длина - 16. Размер блока возьмем - 4. Jump Search найдет значение 55 с помощью следующих шагов:

1. Переход от индекса 0 к индексу 4
2. Переход с индекса 4 к индеку 8
3. Перейсти с индекса 8 к индексу 12
4. Поскольку элемент с индексом 12 больше 55, мы вернемся на шаг назад. Переходим на индекс 8
5. Выполняем линейный поиск с индекса 8, чтобы получить элемент 55

Data Science: Алгоритмы и Структуры данных | Чат 💬