Atlamalı Arama (Jump Search)

#Nasıl çalışır?

Atlamalı arama (jump search), sıralı bir dizide elemanları tek tek değil, √n büyüklüğünde bloklar halinde atlayarak gezer. Her bloğun son elemanına bakılır; aranan değer o elemandan büyükse blok tamamen atlanır.

Aranan değerin bulunduğu blok bulununca yalnızca o blok baştan sona taranır. Böylece hem doğrusal aramadan çok daha az karşılaştırma yapılır hem de ikili aramadaki gibi geri dönüp ileri gitmek gerekmez.

Bu özellik, geri gitmenin pahalı olduğu durumlarda (örneğin bant ya da sıralı erişimli depolama) atlamalı aramayı ikili aramaya tercih edilebilir kılar.

#Canlı animasyon

step = √n; prev = 0
while a[min(step, n) - 1] < target:
  prev = step; step = step + √n   (prev ≥ n → not found)
for i = prev to min(step, n) - 1:
  if a[i] == target: return i
return -1

#Adım adım

1. 01Blok boyunu √n olarak belirle.
2. 02Her bloğun son elemanını aranan değerle karşılaştır.
3. 03Son eleman aranan değerden küçükse bir sonraki bloğa atla.
4. 04Son eleman aranan değerden büyük ya da eşitse o bloğu baştan tek tek tara.
5. 05Dizinin sonuna gelinirse ya da blokta bulunamazsa değer yoktur.

#Örnek kod

Aynı algoritma 8 dilde. Her program derlenip çalıştırılarak test edildi ve hepsi aynı çıktıyı veriyor.

import math


def jump_search(a: list[int], target: int) -> int:
    """a must be sorted. Jumps ahead in blocks of sqrt(n), then scans one block."""
    n = len(a)
    jump = int(math.sqrt(n))
    prev, step = 0, jump
    # Skip whole blocks whose last element is still smaller than the target.
    while a[min(step, n) - 1] < target:
        prev = step
        step += jump
        if prev >= n:
            return -1
    for i in range(prev, min(step, n)):
        if a[i] == target:
            return i
    return -1


numbers = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
print(jump_search(numbers, 13))
print(jump_search(numbers, 4))

#Karmaşıklık

Yaklaşık √n atlama ve en fazla √n adımlık bir tarama yapılır; toplam O(√n). Bu, doğrusal aramanın O(n)'inden iyi, ikili aramanın O(log n)'inden kötüdür. Blok boyu √n seçilir çünkü atlama sayısı (n / m) ile blok taraması (m) toplamı m = √n iken en küçük olur.

#Ne zaman kullanılır?

Veri sıralıysa ama geriye doğru gitmek pahalıysa ya da yalnızca ileri gidilebiliyorsa (sıralı dosyalar, bağlı yapılar üzerinde atlama işaretçileri) kullanışlıdır. Skip list veri yapısının fikri de buna dayanır. Rastgele erişimli dizilerde genellikle ikili arama daha hızlıdır.

#Alıştırma

Soruları cevaplamak ve ilerlemeni kaydetmek için giriş yap.