Arama algoritmaları: doğrusal, ikili, interpolasyon

Bir öğrenci numarasını listede bulmak, bir kelimeyi sözlükte aramak, bir ürünü fiyat listesinde bulmak: hepsi arama problemidir. İki temel strateji var. Doğrusal arama (linear search) baştan sona tek tek bakar, her dizide çalışır ama yavaştır. İkili arama (binary search) sadece sıralı dizide çalışır ama inanılmaz hızlıdır: bir milyon elemanda en fazla 20 adım. Sınavda ikili aramanın low/mid/high iz tablosu, karşılaştırma sayısı ve kodun küçük hataları sorulur.

Altın kurallar:

1. İkili arama sadece sıralı dizide çalışır.
2. Döngü koşulu low <= high. Tek elemanlı aralık da kontrol edilir.
3. Sınırı kaydırırken mid + 1 ve mid - 1.
4. En kötü durumda $\lfloor \log_2 n \rfloor + 1$ karşılaştırma.

Doğrusal arama (linear / sequential search)

static int linearSearch(int[] a, int x) {
    for (int i = 0; i < a.length; i++)
        if (a[i] == x) return i;
    return -1;
}

Hepsi O(n). Avantajı: sıralama gerektirmez, bağlı listede de çalışır. Dizi sıralı olsa bile doğrusal arama bunu kullanmaz; olmayan bir değer için hep sonuna kadar gider (sıralı listede erken çıkış ekleyebilirsin, 3. hafta).

İkili arama (binary search)

Sözlükte kelime ararken ortadan açarsın. Aradığın kelime o sayfadan önce geliyorsa sağ yarıyı tamamen atarsın. Her adımda arama alanı yarıya iner.

static int binarySearch(int[] a, int x) {
    int low = 0, high = a.length - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (a[mid] == x) return mid;
        else if (a[mid] < x) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

İz tablosu

Dizi (indeksler üstte):

indeks:  0  1   2   3   4   5   6   7   8   9
değer:   3  8  12  17  21  25  30  34  41  47

47’yi arama (en sağdaki eleman, en kötü durumlardan biri):

low=0 high=9 mid=4 a[mid]=21
low=5 high=9 mid=7 a[mid]=34
low=8 high=9 mid=8 a[mid]=41
low=9 high=9 mid=9 a[mid]=47
result 9 probes=4

5’i arama (dizide yok):

low=0 high=9 mid=4 a[mid]=21
low=0 high=3 mid=1 a[mid]=8
low=0 high=0 mid=0 a[mid]=3
stop: low=1 high=0
result -1 probes=3

Döngü low > high olunca biter. O anda low, aranan değerin sırayı bozmadan eklenebileceği konumdur (5, indeks 1’e girmeli). Java’nın hazır Arrays.binarySearch metodu bulamayınca -(low) - 1 döner: bu örnekte −2.

İPUCU · İz tablosu düzeni. Sınavda her satıra low | high | mid | a[mid] | karşılaştırma sonucu yaz. mid’i hesaplarken tam sayı bölmesini unutma: (0 + 9) / 2 = 4, 4.5 değil.

Kaç karşılaştırma?

Her probe aralığı yarıya indirir. n elemandan 1 elemana inmek için $\log_2 n$ yarılama gerekir, bir de son elemanı kontrol etmek için 1. En kötü durum $\lfloor \log_2 n \rfloor + 1$:

n=10 worst probes=4 floor(log2 n)+1=4
n=100 worst probes=7 floor(log2 n)+1=7
n=1000 worst probes=10 floor(log2 n)+1=10
n=1000000 worst probes=20 floor(log2 n)+1=20

Bedel: dizinin sıralı olması gerekir. Sıralama en iyi O(n log n) sürer (14. hafta). Tek bir arama için sıralamaya değmez; aynı dizide çok arama yapılacaksa değer.

Özyinelemeli hali

static int binarySearch(int[] a, int x, int low, int high) {
    if (low > high) return -1;
    int mid = low + (high - low) / 2;
    if (a[mid] == x) return mid;
    if (a[mid] < x) return binarySearch(a, x, mid + 1, high);
    return binarySearch(a, x, low, mid - 1);
}

Bağıntı $T(n) = T(n/2) + 1$, çözümü O(log n) (11. hafta). Döngülü versiyon O(1), özyinelemeli versiyon O(log n) ek yığın belleği kullanır.

Üç klasik hata

1. while (low < high). Aralık tek elemana inince döngü o elemana bakmadan biter. {1, 3, 5} üzerinde:

find 1 -> -1  find 3 -> 1  find 5 -> -1  

2. low = mid ya da high = mid. low = 3, high = 4 iken mid = 3; low = mid yazarsan low hiç değişmez, sonsuz döngü.

3. (low + high) / 2 taşması.

int low = 1_500_000_000, high = 2_000_000_000;
System.out.println((low + high) / 2 + " vs " + (low + (high - low) / 2));

-397483648 vs 1750000000

Bu hata Java’nın kendi kütüphanesinde yıllarca kaldı. Çok büyük dizilerde ortaya çıkar; sınavda doğru formülü yazman beklenir.

TUZAK · Sırasız dizide ikili arama. Hata vermez, sessizce yanlış sonuç döndürür. {9, 2, 7, 4, 1, 8, 3} üzerinde 2 ve 8 şans eseri bulunur ama 7 bulunamaz (−1), çünkü algoritma 7’nin bulunduğu sol yarıyı ilk adımda atar.

Tekrarlı değerler

{2, 4, 4, 4, 7} üzerinde standart ikili arama 4 için indeks 2’yi döner, çünkü ilk mid orası. İlk konumu istiyorsan eşleşmede durma: sonucu kaydet ve high = mid - 1 ile solda aramaya devam et. Bu varyasyon indeks 1’i döner. Son konum için simetrik olarak low = mid + 1.

İnterpolasyon araması (interpolation search)

Telefon rehberinde “Yılmaz”ı ararken ortadan değil, sona yakın bir yerden açarsın. İnterpolasyon araması aynısını yapar: hedefin değerine bakarak konumunu tahmin eder.

$pos = low + \frac{(x - a[low]) \cdot (high - low)}{a[high] - a[low]}$

Sonra ikili aramadaki gibi a[pos] ile karşılaştırıp low ya da high’ı kaydırır.

low=0 high=9 pos=6 a[pos]=70
6 probes=1
8 probes(skewed)=9
8 probes(binary)=3

İlk iki satır: {10, 20, ..., 100} dizisinde 70, ilk tahminde bulundu. Son iki satır: {1, 2, ..., 9, 1000} gibi çarpık bir dizide 9’u aramak interpolasyonla 9 probe, ikili aramayla 3 probe sürdü. 1000 değeri tahmini hep sola kaydırıyor.

Sık yapılan hatalar

static int binarySearch(int[] a, int x) {
    int low = 0, high = a.length - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (a[mid] == x) return mid;
        else if (a[mid] < x) low = mid + 1;   // sağ yarı
        else high = mid - 1;                  // sol yarı
    }
    return -1;
}

static int binarySearch(int[] a, int x, int low, int high) {
    if (low > high) return -1;                       // boş aralık
    int mid = low + (high - low) / 2;
    if (a[mid] == x) return mid;
    if (a[mid] < x) return binarySearch(a, x, mid + 1, high);
    return binarySearch(a, x, low, mid - 1);
}

int low = 0, high = a.length - 1;
while (low < high) {
    int mid = (low + high) / 2;
    if (a[mid] == x) return mid;
    else if (a[mid] < x) low = mid + 1;
    else high = mid - 1;
}
return -1;

int low = 0, high = a.length - 1, ans = -1;
while (low <= high) {
    int mid = low + (high - low) / 2;
    if (a[mid] == x) { ans = mid; high = mid - 1; }
    else if (a[mid] < x) low = mid + 1;
    else high = mid - 1;
}
return ans;