Enterpolasyon Araması

#Nasıl çalışır?

Enterpolasyon araması (interpolation search), ikili arama gibi aralığı daraltır ama ortaya değil, değerin olması gereken yere bakar. Telefon rehberinde "Yılmaz" ararken rehberin ortasını değil, sonlara doğru bir sayfayı açmak gibi.

Tahmin edilen yer, aralığın uçlarındaki değerlerle orantı kurularak hesaplanır: aranan değer aralığın değer olarak yüzde kaçındaysa, konum olarak da aşağı yukarı o kadar ilerisine bakılır.

Değerler eşit aralıklarla dağılmışsa tek bir tahminde bulabilir. Dağılım çok dengesizse ise (örneğin 1, 2, 3, 1000000) tahminler kötüleşir ve doğrusal aramaya kadar yavaşlayabilir.

#Canlı animasyon

lo = 0; hi = n - 1
while lo <= hi and a[lo] <= target <= a[hi]:
  pos = lo + (target - a[lo]) · (hi - lo) / (a[hi] - a[lo])
  if a[pos] == target: return pos
  if a[pos] < target: lo = pos + 1 else: hi = pos - 1
return -1

#Adım adım

1. 01lo ve hi ile tüm diziyi aralık olarak al.
2. 02Aranan değer a[lo] ile a[hi] arasında değilse dur: değer yoktur.
3. 03Konumu tahmin et: pos = lo + (aranan − a[lo]) · (hi − lo) / (a[hi] − a[lo]).
4. 04a[pos] aranan değerse bulundu; küçükse lo = pos + 1, büyükse hi = pos − 1 yap.
5. 05Aralık boşalana kadar tekrarla.

#Örnek kod

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

def interpolation_search(a: list[int], target: int) -> int:
    """a must be sorted. Guesses the position from the values instead of taking the middle."""
    lo, hi = 0, len(a) - 1
    while lo <= hi and a[lo] <= target <= a[hi]:
        if a[hi] == a[lo]:
            pos = lo
        else:
            pos = lo + (target - a[lo]) * (hi - lo) // (a[hi] - a[lo])
        if a[pos] == target:
            return pos
        if a[pos] < target:
            lo = pos + 1
        else:
            hi = pos - 1
    return -1


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

#Karmaşıklık

Değerler düzgün dağılmışsa ortalama karşılaştırma sayısı O(log log n)'dir; 1 milyon eleman için 4–5 tahmin. Ama en kötü durumda (çok dengesiz dağılım) her tahmin aralığı yalnızca bir eleman daraltır ve süre O(n)'e çıkar. İkili aramanın O(log n) garantisi burada yoktur.

#Ne zaman kullanılır?

Büyük, sıralı ve değerleri aşağı yukarı düzgün dağılmış veride (ardışık numaralar, zaman damgaları, eşit aralıklı ölçümler) ikili aramadan hızlıdır. Dağılım bilinmiyorsa ya da dengesizse ikili arama daha güvenli bir seçimdir.

#Alıştırma

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