Перейти к поиску

В информатике поиск с переходом или поиск по блокам относится к алгоритму поиска в упорядоченных списках . Это работает, сначала проверяя все элементы L _km , где $k\in \mathbb {N}$ а m — размер блока, пока не будет найден элемент, превышающий размер ключа поиска . Чтобы найти точное положение ключа поиска в списке, линейный поиск выполняется в подсписке L _{[( k -1) m , km ]} .

Оптимальное значение m — √ n где n — длина списка L. , Поскольку на обоих шагах алгоритма рассматривается не более √ n элементов, алгоритм выполняется за O( √ n время ). Это лучше, чем линейный поиск , но хуже, чем бинарный поиск . Преимущество перед последним заключается в том, что при поиске перехода требуется переход назад только один раз, в то время как двоичный файл может переходить назад вверх для регистрации n раз. Это может быть важно, если прыжок назад занимает значительно больше времени, чем прыжок вперед.

Алгоритм можно модифицировать, выполняя несколько уровней перехода с переходом в подсписках, прежде чем, наконец, выполнить линейный поиск . Для перехода на уровень k найдите оптимальный размер блока m _l для l ^й уровень (считая с 1) равен n ^(кл)/к . Модифицированный алгоритм выполнит k прыжков назад и пробежит за O( kn ^{1/( к +1)} ) время.

Выполнение

algorithm JumpSearch is
    input: An ordered list L, its length n and a search key s.
    output: The position of s in L, or nothing if s is not in L.
    
    a ← 0
    b ← ⌊√n⌋
    
    while Lmin(b,n)-1 < s do
        a ← b
        b ← b + ⌊√n⌋
        if a ≥ n then
            return nothing
    
    while La < s do
        a ← a + 1
        if a = min(b, n)
            return nothing
    
    if La = s then
        return a
    else
        return nothing

См. также

• Пропустить список
• Интерполяционный поиск
• Линейный поиск — выполняется за время O( n ), смотрит только вперёд.
• Бинарный поиск — выполняется за время O(log n ), смотрит как вперед, так и назад.

Ссылки

• В этой статье использованы общедоступные материалы из Пол Э. Блэк. «поиск в прыжке» . Словарь алгоритмов и структур данных . НИСТ .
• Бен Шнейдерман , Поиск с переходом: техника быстрого последовательного поиска , CACM, 21(10):831-834, октябрь 1978 г.