Atlamalı Arama
Arama O(√n) O(1)Sıralı dizide √n boyutunda sabit bloklarla ileri sıçrayarak hedefi tutabilecek bloğu bulur, sonra o bloğu doğrusal tarar.
3
7
9
15
23
28
34
41
8 elemanlı sıralı dizi — atlama boyu = ⌊√8⌋ = 2.
DeğişmezŞimdiye kadar geçilen her blok sonu hedeften küçüktü, dolayısıyla hedef o bloklarda olamaz.
1/5
sondaj0step2prev0
jump-search.c
int jumpSearch(int arr[], int n, int target) {int step = (int)sqrt(n);int prev = 0;while (arr[min(step, n) - 1] < target) {prev = step;step += (int)sqrt(n);if (prev >= n)return -1;}while (arr[prev] < target) {prev++;if (prev == min(step, n))return -1;}if (arr[prev] == target)return prev;return -1;}
Atlamalı Arama nasıl çalışır?
Sıralı dizide √n boyutlu bloklarla sıçra; hedefi aşınca önceki bloğu doğrusal tara.
En iyi durum
Hedef blok sınırında: O(1) sıçrama.
En kötü durum
√n sıçrama + √n tarama adımı: O(√n).
Ne zaman kullanılır?
Geriye atlamanın ucuz olduğu ama tam doğrusal taramadan az karşılaştırma istenen sıralı veriler.