Üstel arama

İkili arama, ortaya bakabilmek için listenin nerede bittiğini bilmek zorundadır. Üstel arama ise bilmek zorunda değildir: hedefi geçene kadar giderek büyüyen adımlarla dörtnala ilerler, sonra son adımı ikili aramayla tarar. Bu da onu uzunluğu bilinmeyen listeler için ideal, başa yakın değerler için de hızlı yapar.

1, 2, 4 ve 8. sıralar üzerinde uzunluğu ikiye katlanan sıçramalar içeren sıralı bir çubuk dizisi; son iki sıçrama arasındaki aralık gölgeli
1, 2, 4 ve 8. sıralar üzerinde uzunluğu ikiye katlanan sıçramalar içeren sıralı bir çubuk dizisi; son iki sıçrama arasındaki aralık gölgeli

Fikir

1. sıradaki değeri, sonra 2., 4., 8., 16. ve sonraki sıraları kontrol edin; her sıra bir öncekinin iki katı uzaklıktadır. Oradaki değer hedeften küçük olduğu sürece hedef daha ileride olmalıdır. Bir değer ilk kez küçük olmadığında hedef kıstırılmıştır: bir önceki kontrol edilen sıradan sonradır ve bu sıradan ileride değildir. Bu aralık sıralıdır, dolayısıyla ikili arama hedefi bulur ya da olmadığını gösterir.

Bir örnek

2, 5, 8, 12, 16, 23, 38, 56, 72, 91 listesinde 23'ü arayalım. 1. sırada 2, 2. sırada 5, 4. sırada 12 var; hepsi küçük. 8. sırada 56 var ve bu daha büyük, yani 23 yalnızca 5. ile 7. sıralar arasında olabilir. İkili arama bunların ortasını, 6. sırayı kontrol eder ve 23'ü bulur: 5 karşılaştırma; sade ikili arama ise 3 karşılaştırmayla bulur. Aynı listede 12 arandığında arama 3 karşılaştırmadan sonra 4. sırada durur, ikili aramadan bir eksik; 2 ise 1. sırada tek bir karşılaştırmayla bulunur.

Kaç karşılaştırma

i. sıradaki bir hedef için ikiye katlama yaklaşık log₂ i adımdan sonra durur ve i'den az sıralık bir aralık bırakır; ikili arama bu aralığı yaklaşık log₂ i adım daha harcayarak tarar. Böylece arama, listenin uzunluğu ne olursa olsun yaklaşık 2 log₂ i karşılaştırmaya mal olur. Hedef başa yakınsa bu, her zaman yaklaşık log₂ n ödeyen ikili aramayı geçer. Sona yakınsa üstel arama yaklaşık iki katına kadar fazla öder. 40 değer için uygulama, ilk beş sırada ortalama yaklaşık 3, son beş sırada yaklaşık 9 karşılaştırma yapar; ikili aramada bu sayı yaklaşık 4,6'dır.

Bilinmeyen uzunluk ve dörtnala

Jon Bentley ve Andrew Yao bu ikiye katlama stratejisini 1976'da sınırsız arama için tanımladı: sonu bilinmeyen sıralı bir dizide, örneğin sonsuz bir listede ya da yalnızca tek tek yoklanabilen bir veri akışında bir değer bulmak. Aynı fikir birleştirmeyi de hızlandırır. İki sıralı parçadan biri sürekli kazanırsa Timsort dörtnala (galloping) moduna geçer: bir sonraki değerin nereye gideceğini bulmak için diğer parçada tek tek ilerlemek yerine 1, 2, 4, 8 sıra ileriye bakar.

Kendiniz keşfedin

Uygulamayı açın, Aranan değer alanından bir değer seçin ve Adım'a basın. 1, 2, 4, 8 ve sonraki sıralara her bakış vurgulanır; bir değer küçük olmadığı anda son iki sıra arasındaki aralık gölgelenir ve ikili arama devreye girer. Önce küçük, sonra büyük bir değer arayın ve sayıyı ikili arama kutucuğuyla karşılaştırın.

Sık sorulan sorular

Üstel aramanın zaman karmaşıklığı nedir?

i. sıradaki bir hedef için O(log i), yani n değerli bir listede en fazla O(log n). O(1) ek bellek ve sıralı bir liste gerektirir.

Üstel arama ile ikili arama arasındaki fark nedir?

İkili arama tüm listeyle başlar ve listenin uzunluğuna ihtiyaç duyar. Üstel arama önce ikiye katlayarak hedefi içeren bir aralık bulur, sonra yalnızca o aralığı ikili aramayla tarar. Hedef başa yakınken daha hızlıdır ve uzunluğu bilmeden çalışır.

Neden adıma sabit bir miktar eklemek yerine adım ikiye katlanıyor?

Sabit bir adım eklemek atlamalı aramadır (jump search); listeyi geçmek için yaklaşık n bölü adım kadar bakış gerekir. İkiye katlama i. sıraya yaklaşık log₂ i bakışta ulaşır ve bıraktığı aralık hiçbir zaman gerekenin iki katından büyük olmaz; böylece sonraki ikili arama kısa kalır.

Üstel arama nerede kullanılır?

Sınırsız ya da çok uzun sıralı verilerde arama yapmak, sıralı parçaları birleştirmek (Timsort'taki dörtnala modu) ve hiçbir üst sınır bilinmediğinde bir koşulun doğru olduğu ilk sırayı bulmak için.

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

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

Üstel aramayı deneyin