Aradeğerlemeli Arama

Arama O(log log n) O(1)

Sonda konumunu, hedefin değerinin pencerenin uçlarına oranından tahmin eder — düzgün yayılmış veride O(log log n)'e yakındır.

Boşta

8 elemanlı sıralı dizide 15 aranıyor.

DeğişmezHedef varsa [0..7] aralığındadır. Yoklama, değerlerin eşit dağıldığını varsayarak yeri tahmin eder.

1/5

karşılaştırma0sondaj0lo0hi7pos0

kontrolbulunduelendi

interpolation-search.c

int interpolationSearch(int arr[], int n, int target) {
    int lo = 0, hi = n - 1;
    while (lo <= hi && target >= arr[lo] && target <= arr[hi]) {
        if (lo == hi) {
            if (arr[lo] == target) return lo;
            return -1;
        }
        if (arr[hi] == arr[lo])   /* flat window: all equal */
            return lo;            /* loop guard => match    */
        int pos = lo + (target - arr[lo]) * (hi - lo)
                       / (arr[hi] - arr[lo]);
        if (arr[pos] == target)
            return pos;
        if (arr[pos] < target)
            lo = pos + 1;
        else
            hi = pos - 1;
    }
    return -1;
}

Aradeğerlemeli Arama nasıl çalışır?

Ortayı değil, hedefin orantısal olarak olması gereken yeri yokla: pencere uç değerlerinin %90'ı kadarsa %90'lık konuma bak. Sözlüğü doğru harfe yakın açmak gibi.

En iyi durum

Düzgün dağılmış anahtarlar: O(log log n) yoklama.

En kötü durum

Çarpık dağılımlar (ör. üstel): O(n)'e düşer.

Ne zaman kullanılır?

Anahtarları düzgün dağılıma yakın büyük sıralı diziler.