İkili axtarışdan başqa çeşidlənmiş məlumatda axtarmağın digər üsulları da var. Hər biri müəyyən şərtlərdə üstündür: tullanma axtarışı (O(sqrt n)) yalnız irəli keçid olanda, interpolyasiya bərabər paylanmış dəyərlərdə (orta O(log log n)), eksponensial axtarış isə uzunluğu bilinməyən ardıcıllıqlarda. Əsası ikili axtarış mövzusunda öyrəndiniz.

16 elementdə addım 4 ilə tullanma axtarışı
16 elementdə addım 4 ilə tullanma axtarışı

Tullanma axtarışı (jump search)

Massivi step ölçülü bloklara bölürük. Blokun son elementi x-dən kiçik olduqca növbəti bloka tullanırıq; a[cur - 1] >= x olanda hədəf cari blokdadır və onu xətti axtarırıq. Yoxlamaların sayı n / step + step-dir, step = sqrt n olanda minimaldır: O(sqrt n). Yaddaş O(1). İkili axtarışdan yavaşdır, amma yalnız irəli gedir: geri qayıtmaq bahalı olan mühitdə (lent, bəzi iterator tipləri) faydalıdır.

python
import math

def linear(a, x):
    probes = 0
    for i, v in enumerate(a):
        probes += 1
        if v == x:
            return i, probes
    return -1, probes

def jump(a, x):
    n = len(a)
    step = math.isqrt(n)
    probes, prev, cur = 0, 0, step
    while prev < n:                         # jump over whole blocks
        probes += 1
        if a[min(cur, n) - 1] >= x:
            break
        prev, cur = cur, cur + step
    for i in range(prev, min(cur, n)):      # scan inside the block
        probes += 1
        if a[i] == x:
            return i, probes
        if a[i] > x:
            break
    return -1, probes