Atlamalı arama

Atlamalı arama, içindekiler sayfası olmayan bir kitapta bir sayfayı aramaya benzer: sayfa numaralarına göz atarak birer parça ileri çevirirsiniz, çok ileri gittiğinizde de son parçayı geri çevirerek gözden geçirirsiniz. Sıralı bir listede, her değeri kontrol etmekten çok daha az karşılaştırma gerektirir.

Bloklara bölünmüş sıralı bir çubuk dizisi; atlanan her bloğun son çubuğu soluk, hedefi içerebilecek blok gölgeli
Bloklara bölünmüş sıralı bir çubuk dizisi; atlanan her bloğun son çubuğu soluk, hedefi içerebilecek blok gölgeli

Fikir

Sıralı bir listede bir bloğun son değeri, hedefin o blokta olup olamayacağını söyler: son değer hedeften küçükse bloktaki her değer de küçüktür. Yani içine bakmaya gerek yoktur. Her bloğun son değerine sırayla bakın ve bütün blokları atlayın; ta ki biri hedeften küçük olmayana kadar. O zaman hedef yalnızca o blokta olabilir: bloğu başından tarayın.

Bir örnek

2, 5, 8, 12, 16, 23, 38, 56, 72, 91 listesinde 3'lük bloklarla 23'ü arayın. İlk blok 8 ile biter; bu daha küçüktür, o yüzden bloğu atlayın. İkinci blok 23 ile biter; bu küçük değildir, o yüzden 23 yalnızca 12, 16, 23 içinde olabilir. Tarama 12, 16 ve ardından 23'ü verir: 5 karşılaştırmada bulundu; doğrusal arama 6, ikili arama 3 karşılaştırma gerektirir. 40 arandığında 8, 23 ve 72 blok sonları 38, 56, 72 bloğuna götürür; 38 küçük, 56 ise zaten büyüktür, yani 40 orada yoktur: yine 5 karşılaştırma.

Neden √n

m değerlik bloklarla doğru bloğu bulmak en fazla yaklaşık n/m, onu taramak en fazla m karşılaştırma alır. Az sayıda uzun atlama taramayı uzatır; çok sayıda kısa atlama atlamayı uzatır. n/m + m toplamı, iki kısım eşit olduğunda, yani m = √n iken en küçüktür ve yaklaşık 2√n olur. 40 değer için bu, 6'lık bloklar ve en fazla 13 karşılaştırma demektir; bir milyon değer için 1.000'lik bloklar ve yaklaşık 2.000 karşılaştırma.

Nerede işe yarar

İkili arama daha az karşılaştırma gerektirir, yaklaşık log₂ n. Ama ikili arama listenin her yerine ileri geri atlar; atlamalı arama ise yalnızca ileri gider ve bir kez, bir bloğun başına geri döner. Bu da onu, geri gitmenin yavaş olduğu teyp üzerindeki ya da bağlı bir yapıdaki veriler için cazip kıldı. Ben Shneiderman bunu 1978'de jump searching olarak tanımladı. Aynı √n bloğa bölme fikri, çoğu zaman karekök ayrışımı olarak anılır ve başka birçok algoritmada da karşımıza çıkar.

Ben Shneiderman (solda) 2012 Webshop’ta Catherine Plaisant ile. Shneiderman atlamalı aramayı 1978’de tarif etti.
Ben Shneiderman (solda) 2012 Webshop’ta Catherine Plaisant ile. Shneiderman atlamalı aramayı 1978’de tarif etti.

Keşfedin

Uygulamayı açın, Aranan değer alanında bir değer seçin ve Adım'a basın. Her atlama bir bloğun son değerini vurgular; atlanan bloklar solar, hedefi içerebilecek blok ise taranırken gölgeli görünür. 40 çubukla Atlama boyu ayarını √n yerine 2 ya da 8 yapın ve atlamalar ile tarama arasındaki dengenin nasıl kaydığını izleyin.

Sık sorulan sorular

Atlamalı aramanın zaman karmaşıklığı nedir?

√n değerlik bloklarla O(√n): en fazla yaklaşık 2√n karşılaştırma. O(1) ek bellek ve sıralı bir liste gerektirir.

Atlamalı arama ile ikili arama arasındaki fark nedir?

İkili arama her seferinde kalan kısmı ikiye böler ve yaklaşık log₂ n karşılaştırma gerektirir, ama ileri geri hareket eder. Atlamalı arama sabit adımlarla ileri atlar ve tek bir bloğu tarar; yaklaşık 2√n karşılaştırma gerektirir ve yalnızca bir kez geri döner.

Son bloktaki tarama yerine ikili arama kullanılabilir mi?

Evet. Bloğu ikili aramayla aramak taramayı m karşılaştırmadan yaklaşık log₂ m'ye indirir. Atlamalar yine n/m tutar, bu yüzden o zaman daha büyük bloklar kârlı olur.

Atlamalı arama sıralı bir liste gerektirir mi?

Evet. Bir bloğu atlamak yalnızca, son değerinin küçük olması bloktaki her değerin küçük olduğu anlamına geldiği için güvenlidir. Uygulama sırasız bir listeyi önce sıralar.

Denemeye hazır mısınız?

PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.

Atlamalı aramayı deneyin