Üstel Arama (Exponential Search)

#Nasıl çalışır?

Üstel arama (exponential search), sıralı bir dizide önce aranan değerin bulunabileceği aralığı bulur, sonra o aralıkta ikili arama yapar.

Aralığı bulmak için sınır 1, 2, 4, 8, … diye ikiye katlanır; sınırdaki değer aranan değeri geçince durulur. Aranan değer son iki sınır arasında olmalıdır.

Aranan değer dizinin başına yakınsa çok hızlıdır; ayrıca dizinin uzunluğunu bilmeden (sınırsız ya da akan veride) arama yapmaya imkân verir.

#Canlı animasyon

if a[0] == target: return 0
bound = 1
while bound < n and a[bound] < target: bound = bound · 2
lo = bound / 2; hi = min(bound, n - 1)
binary search in a[lo..hi]
return -1

#Adım adım

1. 01İlk elemana bak; aranan değerse bitti.
2. 02Sınırı 1'den başlat.
3. 03a[sınır] aranan değerden küçük olduğu sürece sınırı ikiye katla.
4. 04Aranan değer [sınır/2, sınır] aralığında olmalı.
5. 05Bu aralıkta ikili arama yap.

#Örnek kod

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

def binary_search(a: list[int], lo: int, hi: int, target: int) -> int:
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == target:
            return mid
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1


def exponential_search(a: list[int], target: int) -> int:
    """a must be sorted. Doubles a bound until it passes the target, then binary searches behind it."""
    if not a:
        return -1
    if a[0] == target:
        return 0
    bound = 1
    while bound < len(a) and a[bound] < target:
        bound *= 2
    return binary_search(a, bound // 2, min(bound, len(a) - 1), target)


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

#Karmaşıklık

i, aranan değerin konumudur. Sınırı bulmak log i, ardından aralıktaki ikili arama yine log i adım sürer. Yani değer başa yakınsa n çok büyük olsa bile arama kısa sürer. En kötü durumda O(log n), ikili aramayla aynıdır.

#Ne zaman kullanılır?

Boyutu bilinmeyen ya da çok büyük sıralı veride (sınırsız listeler, sayfa sayfa gelen sonuçlar) ve aranan değerlerin çoğunlukla başa yakın olduğu durumlarda kullanılır. Bazı kütüphanelerde galloping (dörtnala) arama adıyla, Timsort'un birleştirme adımında da kullanılır.

#Alıştırma

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