В информатике поиск с переходом или блочный поиск относится к алгоритму поиска для упорядоченных списков . Он работает, сначала проверяя все элементы L km , где m — размер блока, пока не будет найден элемент, который больше ключа поиска. Чтобы найти точное положение ключа поиска в списке, выполняется линейный поиск по подсписку L [( k -1) m , km ] .
Оптимальное значение m равно √ n , где n — длина списка L . Поскольку оба шага алгоритма просматривают максимум √ n элементов, алгоритм выполняется за время O( √ n ). Это лучше, чем линейный поиск , но хуже, чем двоичный поиск . Преимущество перед последним заключается в том, что поиск с переходом должен перейти назад только один раз, в то время как двоичный поиск может перейти назад до log n раз. Это может быть важно, если переход назад занимает значительно больше времени, чем переход вперед.
Алгоритм можно модифицировать, выполняя несколько уровней поиска скачков в подсписках, прежде чем, наконец, выполнить линейный поиск . Для поиска скачков на k -м уровне оптимальный размер блока m l для l -го уровня (начиная с 1) равен n (kl)/k . Модифицированный алгоритм выполнит k обратных скачков и будет работать за время O( kn 1/( k +1) ).
Алгоритм JumpSearch принимает на вход: упорядоченный список L , его длину n и ключ поиска s . Выход: позиция s в L или ничего , если s отсутствует в L. а ← 0 б ← ⌊√ н ⌋ в то время как L min( b , n )-1 < s do a ← b b ← b + ⌊√ n ⌋ если a ≥ n то ничего не возвращать в то время как L a < s do a ← a + 1 if a = min( b , n ) вернуть ничего если L a = s , то вернуть a , иначе ничего не вернуть
В этой статье использованы материалы, находящиеся в открытом доступе, от Пола Э. Блэка. "перейти к поиску". Словарь алгоритмов и структур данных . NIST .