Hafta 6 — Arama ve Hash'leme¶

CEN207 Veri Yapıları (eski adıyla CE205) · Güz 2026–2027

Sunumun içine tıklayıp ok tuşlarıyla ilerleyin; tam ekran için sunumun sağ altındaki düğmeyi ya da yukarıdaki "Sunumu tam ekran aç" bağlantısını kullanın.

0. Başlamadan önce¶

0.1 Zaten bildikleriniz¶

Son beş haftadan iki fikir bu hafta en çok işe yarayacak.

Hafta 1'den — diziler ve indeksler. Bir dizi, elemanlarını tek, bitişik bir bellek bloğunda saklar ve arr[i], doğrudan taban_adres + i * eleman_boyutu olarak hesaplanır — i indeksine ulaşmak için hiçbir arama gerekmez, yalnızca hangi i'nin aradığınızı tuttuğuna karar vermek gerekir. Bu haftaki her arama tekniği (sıçramalı, enterpolasyon, üstel, Fibonacci), sıralı (sorted) bir dizide, aradığınız i'yi olabilecek en az karşılaştırmayla bulmak için hangi indekslerin kontrol edileceğine dair farklı bir stratejidir. Zaten tanıdığınız ikili arama, bu tasarım uzayındaki bir noktadır; bu hafta geri kalanını dolduruyor.

Hafta 4'ten — arama uzayını ikiye bölmek. İkili aramanın büyük fikri — tek bir karşılaştırmayla kalan adayların yarısını elemek, toplamda O(log n) karşılaştırma vermek — bu bölümdeki her tekniğin ölçüldüğü referans noktasıdır. Sıçramalı arama, sadelik karşılığında bilerek ikili aramadan daha kötü sonuç verir; enterpolasyon araması doğru türden veride daha iyi sonuç verir; üstel arama, ikili aramayı önceden bilmediğiniz dizi boyutlarına uyarlar; Fibonacci araması, yalnızca toplama ve çıkarma kullanarak ikili aramanın asimptotik maliyetini yakalar. Bu dört tekniğin hepsi için O(log n)'i aklınızda referans noktası olarak tutun.

Gerçekten yeni bir fikir: sırayı hesaplamayla takas etmek. Yukarıdaki her teknik, target'ı dizi elemanlarıyla karşılaştırarak ve bir aralığı daraltarak çalışmaya devam eder. Hash'leme bu yaklaşımın tamamından vazgeçer: daraltmak yerine, bir hash fonksiyonu, bir anahtarın nerede olduğunu tek bir O(1) adımda doğrudan hesaplar, veride hiçbir sıralama şartı olmadan. Bunun bedeli, iki farklı anahtarın aynı konuma hesaplanabilmesidir — bir çakışma (collision) — ve bu haftanın ikinci yarısı tamamen bunu ele almakla ilgilidir.

0.2 Bu haftanın haritası¶

flowchart TD
    W6["Hafta 6: Arama ve Hash'leme"]
    W6 --> S["Ikili aramanin otesinde (hala karsilastirmaya dayali, hala SIRALI bir dizi gerekir)"]
    S --> S1["Sicramali arama: sabit boyutlu bloklar, O(sqrt n)"]
    S --> S2["Enterpolasyon aramasi: konumu bir formulle tahmin eder"]
    S --> S3["Ustel arama: bir siniri ikiye katlar, sonra icinde ikili arama"]
    S --> S4["Fibonacci aramasi: Fibonacci sayilariyla boler, yalniz +/-"]
    W6 --> H["Hash'leme: karsilastirmak yerine konumu hesaplar"]
    H --> H1["Hash fonksiyonu: h(k) = k mod m (bolme yontemi)"]
    H --> H2["Cakismalar kacinilmazdir -- iki anahtar, bir hucre"]
    H2 --> C1["Ayrik zincirleme: her hucrede bir bagli liste"]
    H2 --> C2["Acik adresleme: anahtar tablonun ICINDE yasar"]
    C2 --> O1["Dogrusal yoklama: h, h+1, h+2, ... (birincil kumelenme)"]
    C2 --> O2["Karesel yoklama: h+1^2, h+2^2, ... (m asal, alpha <= 0.5 gerekir)"]
    C2 --> O3["Cift hash: h1(k), adim h2(k) (pratikte en iyi dagilim)"]
    H --> R["Yeniden hash'leme: tablo dolunca buyur, amortize O(1) ekleme"]

Aşağıda her kutu kendi bölümünü alır — çoğunda adım adım bir animasyon, tam bir C ve Java programı, ve karmaşıklık ile sık yapılan hatalar üzerine bir not vardır.

1. Arama problemi, ve doğrusal ile ikili aramanın tekrarı¶

1.1 Problem, yeniden ifade edilmiş¶

Bu problemin temel halini zaten Hafta 1'de çözdünüz: bir dizi ve bir target değeri verildiğinde, target dizide var mı, ve varsa hangi indekste? Hafta 1 size iki cevap verdi — doğrusal arama (linear search) (her elemanı kontrol et, O(n)) ve ikili arama (binary search) (sıralı bir dizide, tekrar tekrar ortadaki elemana bak ve yarısını ele, O(log n)). Bu haftanın sorusu daha keskin: dizi sıralı olduğuna göre, ikili aramanın O(log n)'i gerçekten yapabileceğimizin en iyisi mi, ve daha iyisini yapmanın ya da daha basit bir fikirle neredeyse aynı iyilikte yapmanın bedeli nedir? Aşağıdaki dört yeni teknik bu soruyu farklı biçimlerde cevaplıyor.

1.2 Tekrar: doğrusal arama, O(n)¶

Doğrusal arama veri hakkında hiçbir varsayımda bulunmaz: arr[0]'ı kontrol eder, sonra arr[1]'i, ve böyle devam eder, target'ı bulana ya da dizi bitene kadar. Maliyeti en kötü durumda (hedef sonuncu ya da yok) ve ortalamada (rastgele tek düze bir konumda bulunan bir hedef için ortalama n/2 eleman kontrol edilir) n, dizinin boyutu, ile orantılıdır. En büyük erdemi, sıralı olsun olmasın her dizide çalışmasıdır — buradan itibaren her teknik, hız karşılığında bu genelliği terk ederek diziyi önce sıralı olmaya zorlar.

1.3 Tekrar: ikili arama, O(log n)¶

İkili arama sıralı bir dizi gerektirir. Ortadaki elemana bakar; hedef oysa biter; hedef daha küçükse, sağ yarının tamamı — ortadaki dahil — tek adımda elenebilir (sıralı düzen, hedefin orada olamayacağını garanti eder); daha büyükse, sol yarı aynı şekilde elenir. Her karşılaştırma kalan adayları ikiye böler, dolayısıyla k karşılaştırmadan sonra en fazla n / 2^k aday kalır; arama bu sayı 1'e ulaştığında biter, bu da en kötü durumda k = log2(n) karşılaştırma verir — O(log n). n = 1.000.000 için bu yaklaşık 20 karşılaştırmadır, aynı veri için doğrusal aramanın bir milyona kadar çıkabilen karşılaştırma sayısına karşılık.

İkili arama, karmaşıklığı ve C/Java kodu aklınızda taze değilse, devam etmeden önce Hafta 1'i tekrar gözden geçirin — bu bölüm onu varsayar ve yeniden türetmeyecektir. Aşağıdaki dört teknik hâlâ sıralı bir dizi gerektirir, ve hâlâ temelde karşılaştırmaya dayalıdır; hiçbiri, doğru türden veride enterpolasyon araması dışında (ve o bile bölüm 3'te göreceğiniz gibi kötü bir en kötü durumla gelir), ikili aramanın O(log n) en kötü durumunu sabit bir çarpandan fazla geçmez.

2. Sıçramalı arama (jump search)¶

2.1 Başlangıç sorusu¶

İkili aramanın tam ortaya zıplaması güçlüdür, ama her tek adımda bir bölme (ya da kaydırma) ve dikkatli bir indeks aritmetiği (lo + (hi - lo) / 2, taşmayı önlemek için) gerektirir, ve belleğe sıralı erişmez — dizide her yere zıplar, bu da bitişik bloklar halinde bellek okumayı seven donanım için dostane değildir (bu dersin bellek hiyerarşisine ve önbelleğe (cache) geldiğinde daha derinlemesine karşılaşacağınız bir gerçek). Peki ya onun yerine ileriye doğru sabit boyutlu bloklar halinde tarasaydık — her k'ıncı elemanı kontrol edip, hedefin olması gereken yeri geçtiğimiz anda, yalnızca o bir bloğu düz bir doğrusal taramaya dönseydik? İşte bu sıçramalı arama (jump search): ikili aramadan daha basit aritmetik, her blok içinde sıralı bellek erişimi, karşılığında ikili aramadan asimptotik olarak yavaş olmak (yine de doğrusal aramadan çok daha hızlı).

Bu blok tarzı arama, Donald Knuth'un The Art of Computer Programming, Volume 3: Sorting and Searching (1973) kitabında ikili aramaya bir alternatif olarak yer alır — özellikle, basit bir kalkülüs argümanının (iki maliyetin toplamını en aza indirmenin) algoritmanın tek serbest parametresini, blok boyutunu, belirlediği bir örnek olarak sunulur.

2.2 Fikir ve doğru blok boyutu¶

Bir blok boyutu b seçin. arr[b-1], arr[2b-1], arr[3b-1], … kontrol edin, target'tan >= olan bir sınır bulana (ya da dizinin sonuna gelene) kadar; target, varsa, o sınırdan hemen önceki blokta olmalıdır (yine sıralı düzen sayesinde). Sonra o tek bloğu soldan sağa, doğrusal olarak tarayın, her elemanı karşılaştırarak.

Bu, en kötü durumda kaç karşılaştırmaya mal olur? Sıçramak en fazla n / b karşılaştırmaya mal olur (diziyi b boyutlu bloklar halinde baştan sona zıplarsınız), ve son doğrusal tarama en fazla b karşılaştırmaya mal olur. Toplam: n/b + b. Kalkülüs (ya da yalnızca değerleri deneyerek) bu toplamın b = sqrt(n) olduğunda en aza indiğini gösterir, bu da en kötü durumda 2 * sqrt(n) toplam maliyet verir — O(sqrt(n)). Bu, ikili aramanın O(log n)'inden daha kötüdür (n = 1.000.000 için sqrt(n) = 1000 iken log2(n) ≈ 20), ama doğrusal aramanın O(n)'inden çok daha iyidir, ve her adımdaki aritmetik yalnızca bir toplama işlemidir, bir bölme değil.

2.3 Bellekte nasıl durur, ve kod¶

Aşağıda, jump_search, block = floor(sqrt(n)) hesaplar, her seferinde bir blok ileri zıplar (her bloğun son indeksine bakarak), ve son indeksi target'tan >= olan bir blok bulduğunda, o bloğu doğrusal olarak tarar.

int jump_search(const int arr[], int n, int target, int *comparisons) {
    int block = (int) sqrt((double) n);      /* block size = floor(sqrt(n)) */
    if (block < 1) block = 1;
    int prev = 0, step = block, comp = 0;
    while (step < n) {                        /* jump forward one block at a time */
        comp++;
        if (arr[step - 1] >= target) break;    /* target may be in this block */
        prev = step;
        step += block;
    }
    if (step > n) step = n;
    for (int i = prev; i < step; i++) {        /* linear scan inside the block */
        comp++;
        if (arr[i] == target) { *comparisons = comp; return i; }
        if (arr[i] > target) break;             /* sorted: no need to look further */
    }
    *comparisons = comp;
    return -1;
}

static int jumpSearch(int[] arr, int target) {
    int n = arr.length;
    int block = (int) Math.sqrt(n);          // block size = floor(sqrt(n))
    if (block < 1) block = 1;
    int prev = 0, step = block;
    comparisons = 0;
    while (step < n) {                        // jump forward one block at a time
        comparisons++;
        if (arr[step - 1] >= target) break;    // target may be in this block
        prev = step;
        step += block;
    }
    if (step > n) step = n;
    for (int i = prev; i < step; i++) {        // linear scan inside the block
        comparisons++;
        if (arr[i] == target) return i;
        if (arr[i] > target) break;             // sorted: no need to look further
    }
    return -1;
}

Blok sınırlarının tek tek kontrol edildiğini, sonra son bloğun soldan sağa tarandığını izlemek için animasyonu oynatın.

Oynatıcıda ayrıca şunları da deneyin: hedef son bloğa yakın, en çok sıçrama gerekir (zor) ve uç durumlar hedef en küçükten de küçük, hedef en büyükten de büyük, ve hedef aralıkta ama dizide yok — ya da dört zorluk seviyesinde rastgele veri için 🎲'ye basın, ya da kendi sıralı diziniz ve hedefinizi yazın.

2.4 Dene¶

/* Week 6 -- Search and Hashing
 * Jump search: on a SORTED array, jump forward in fixed-size blocks
 * (block = floor(sqrt(n))) until a block boundary is >= target, then scan
 * that block linearly. Prints every jump and every comparison inside the
 * final block.
 * CEN207 Data Structures (formerly CE205)
 */
#include <stdio.h>
#include <math.h>

int jump_search(const int arr[], int n, int target, int *comparisons) {
    int block = (int) sqrt((double) n);      /* block size = floor(sqrt(n)) */
    if (block < 1) block = 1;
    int prev = 0, step = block, comp = 0;
    while (step < n) {                        /* jump forward one block at a time */
        comp++;
        printf("  jump: check arr[%d] = %d\n", step - 1, arr[step - 1]);
        if (arr[step - 1] >= target) break;    /* target may be in this block */
        prev = step;
        step += block;
    }
    if (step > n) step = n;
    printf("  scanning block [%d..%d)\n", prev, step);
    for (int i = prev; i < step; i++) {        /* linear scan inside the block */
        comp++;
        printf("  compare arr[%d] = %d\n", i, arr[i]);
        if (arr[i] == target) { *comparisons = comp; return i; }
        if (arr[i] > target) break;             /* sorted: no need to look further */
    }
    *comparisons = comp;
    return -1;
}

static void print_array(const int arr[], int n) {
    printf("arr =");
    for (int i = 0; i < n; i++) printf(" %d", arr[i]);
    printf("\n");
}

static void run_scenario(const char *label, const int arr[], int n, int target) {
    printf("-- %s --\n", label);
    print_array(arr, n);
    printf("target = %d\n", target);
    int comparisons = 0;
    int index = jump_search(arr, n, target, &comparisons);
    if (index == -1) printf("result: not found, %d comparisons\n\n", comparisons);
    else printf("result: found at index %d, %d comparisons\n\n", index, comparisons);
}

int main(void) {
    int a[] = {2, 6, 10, 14, 18, 22, 26, 30, 34, 38, 42, 46, 50, 54, 58, 62};
    int n = 16;

    run_scenario("normal: 16 values, target found in the second block", a, n, 42);
    run_scenario("hard: target near the last block, needs the most jumps", a, n, 58);
    run_scenario("edge: target is smaller than every value", a, n, 1);
    run_scenario("edge: target is larger than every value", a, n, 999);
    run_scenario("edge: target is in range but not in the array", a, n, 45);

    return 0;
}

/* Week 6 -- Search and Hashing
 * Jump search: on a SORTED array, jump forward in fixed-size blocks
 * (block = floor(sqrt(n))) until a block boundary is >= target, then scan
 * that block linearly. Prints every jump and every comparison inside the
 * final block.
 * CEN207 Data Structures (formerly CE205)
 */
public class JumpSearch {
    static int comparisons;

    static int jumpSearch(int[] arr, int target) {
        int n = arr.length;
        int block = (int) Math.sqrt(n);          // block size = floor(sqrt(n))
        if (block < 1) block = 1;
        int prev = 0, step = block;
        comparisons = 0;
        while (step < n) {                        // jump forward one block at a time
            comparisons++;
            System.out.println("  jump: check arr[" + (step - 1) + "] = " + arr[step - 1]);
            if (arr[step - 1] >= target) break;    // target may be in this block
            prev = step;
            step += block;
        }
        if (step > n) step = n;
        System.out.println("  scanning block [" + prev + ".." + step + ")");
        for (int i = prev; i < step; i++) {        // linear scan inside the block
            comparisons++;
            System.out.println("  compare arr[" + i + "] = " + arr[i]);
            if (arr[i] == target) return i;
            if (arr[i] > target) break;             // sorted: no need to look further
        }
        return -1;
    }

    static void printArray(int[] arr) {
        StringBuilder sb = new StringBuilder("arr =");
        for (int v : arr) sb.append(' ').append(v);
        System.out.println(sb);
    }

    static void runScenario(String label, int[] arr, int target) {
        System.out.println("-- " + label + " --");
        printArray(arr);
        System.out.println("target = " + target);
        int index = jumpSearch(arr, target);
        if (index == -1) System.out.println("result: not found, " + comparisons + " comparisons");
        else System.out.println("result: found at index " + index + ", " + comparisons + " comparisons");
        System.out.println();
    }

    public static void main(String[] args) {
        int[] a = {2, 6, 10, 14, 18, 22, 26, 30, 34, 38, 42, 46, 50, 54, 58, 62};

        runScenario("normal: 16 values, target found in the second block", a, 42);
        runScenario("hard: target near the last block, needs the most jumps", a, 58);
        runScenario("edge: target is smaller than every value", a, 1);
        runScenario("edge: target is larger than every value", a, 999);
        runScenario("edge: target is in range but not in the array", a, 45);
    }
}

Dene

gcc -std=c11 -Wall -Wextra -o /tmp/x jump_search.c && /tmp/x

-- normal: 16 values, target found in the second block --
arr = 2 6 10 14 18 22 26 30 34 38 42 46 50 54 58 62
target = 42
  jump: check arr[3] = 14
  jump: check arr[7] = 30
  jump: check arr[11] = 46
  scanning block [8..12)
  compare arr[8] = 34
  compare arr[9] = 38
  compare arr[10] = 42
result: found at index 10, 6 comparisons

-- hard: target near the last block, needs the most jumps --
arr = 2 6 10 14 18 22 26 30 34 38 42 46 50 54 58 62
target = 58
  jump: check arr[3] = 14
  jump: check arr[7] = 30
  jump: check arr[11] = 46
  scanning block [12..16)
  compare arr[12] = 50
  compare arr[13] = 54
  compare arr[14] = 58
result: found at index 14, 6 comparisons

-- edge: target is smaller than every value --
arr = 2 6 10 14 18 22 26 30 34 38 42 46 50 54 58 62
target = 1
  jump: check arr[3] = 14
  scanning block [0..4)
  compare arr[0] = 2
result: not found, 2 comparisons

-- edge: target is larger than every value --
arr = 2 6 10 14 18 22 26 30 34 38 42 46 50 54 58 62
target = 999
  jump: check arr[3] = 14
  jump: check arr[7] = 30
  jump: check arr[11] = 46
  scanning block [12..16)
  compare arr[12] = 50
  compare arr[13] = 54
  compare arr[14] = 58
  compare arr[15] = 62
result: not found, 7 comparisons

-- edge: target is in range but not in the array --
arr = 2 6 10 14 18 22 26 30 34 38 42 46 50 54 58 62
target = 45
  jump: check arr[3] = 14
  jump: check arr[7] = 30
  jump: check arr[11] = 46
  scanning block [8..12)
  compare arr[8] = 34
  compare arr[9] = 38
  compare arr[10] = 42
  compare arr[11] = 46
result: not found, 7 comparisons

javac -Xlint:all -d /tmp/j JumpSearch.java && java -cp /tmp/j JumpSearch

2.5 Karmaşıklık, hatalar, kendini sına¶

Karmaşıklık. En iyi durum O(1) (hedef, kontrol edilen ilk blok sınırıdır ve >= yerine tam olarak eşit çıkar — nadir, çünkü sınır kontrolü == değil >='dir). En kötü durum ve ortalama durum ikisi de O(sqrt(n))'dir, bölüm 2.2'de türetilen en uygun blok boyutu b = sqrt(n) ile. İkili arama gibi sıralı bir dizi gerektirir.

3. Enterpolasyon araması (interpolation search)¶

3.1 Başlangıç sorusu¶

Kağıt bir telefon rehberinde (ya da basılı bir sözlükte) bir ismi nasıl aradığınızı düşünün. İkili aramanın yapacağı gibi her seferinde tam ortadan açmazsınız. "Yılmaz" arıyorsanız, kitabı sona çok daha yakın bir yerden açarsınız; "Aydın" arıyorsanız, başa çok daha yakın bir yerden. İsimlerin yalnızca sıralı olmadığını, aynı zamanda alfabe boyunca kabaca tek düze (uniform) yayıldığını kullanarak, doğru sayfaya dair iyi bir tahmine doğrudan zıplıyorsunuzdur. Enterpolasyon araması, bunu sayılardan oluşan sıralı bir dizide tam olarak yapar: her zaman ortadakine bakmak yerine, target'ın mevcut aralıktaki en küçük ve en büyük değerler arasında ne kadar ileride durduğunu kullanarak, bir formülle tahmini bir konum hesaplar.

Sıralı veride arama için bu konum-tahmin etme fikri, W. W. Peterson'ın 1957 tarihli Addressing for Random-Access Storage (IBM Journal of Research and Development) makalesinde görülür — bu haftanın ileride hash'leme bölümlerinin de dayandığı, rastgele erişimli depolamayı düzenlemeye dair temel fikirleri ortaya koyan aynı erken makale — ve daha sonra enterpolasyon araması (interpolation search) adı altında biçimselleştirilip analiz edilmiştir.

3.2 Formül¶

Mevcut [lo..hi] aralığında, değerlerin arr[lo] ile arr[hi] arasında kabaca eşit aralıklarla dağıldığını varsayın. O zaman target'ın konumu orantısal olarak tahmin edilebilir:

pos = lo + floor( (target - arr[lo]) * (hi - lo) / (arr[hi] - arr[lo]) )

target == arr[lo] ise, bu pos = lo verir; target == arr[hi] ise, pos = hi verir; arada bir değer için, doğrusal olarak tahmin eder. arr[pos]'u target ile, ikili aramanın arr[mid]'i karşılaştırdığı gibi karşılaştırın: eşitse, biter; küçükse, [pos+1..hi]'a daraltın; büyükse, [lo..pos-1]'e daraltın. Bir ek durum bir koruma (guard) gerektirir: arr[hi] == arr[lo] ise, formülün paydası sıfırdır — bir sıfıra bölme — bu yalnızca mevcut aralığın tamamı tek bir tekrarlanan değer olduğunda gerçekleşebilir; koruma bu durumu, formülü hiç değerlendirmeden doğrudan yakalar ve çözer.

3.3 Maliyet: tek düze veride mükemmel, çarpık veride zayıf¶

Gerçekten tek düze dağılmış veride, enterpolasyon aramasının tahmini neredeyse her seferinde gerçek konuma çok yakın düşer, bu da ortalama durumda O(log log n) maliyet verir — n = 1.000.000 için, log2(n) ≈ 20 ama log2(log2(n)) ≈ 4,3: yaklaşık yirmi yerine bir avuç yoklama. Ama formülün doğruluğu tamamen tek düze dağılım varsayımına bağlıdır. Çarpık (skewed) veride — diyelim ki birlikte kümelenmiş on altı küçük değer artı bir devasa aykırı değer (outlier) — formülün tahmini o tek aykırı değer tarafından hedeften çok uzaklaştırılır, ve enterpolasyon aramasının en kötü durumu tamamen O(n)'e düşer, doğrusal aramadan daha iyi değil. Enterpolasyon araması bir bahistir: iyi huylu sayısal veride (telefon numaraları, sensör okumaları, zaman damgaları) büyük kazanır, çarpık ya da düşmanca veride kötü kaybeder.

3.4 Bellekte nasıl durur, ve kod¶

int interpolation_search(const int arr[], int n, int target, int *probes) {
    int lo = 0, hi = n - 1, p = 0;
    while (lo <= hi && target >= arr[lo] && target <= arr[hi]) {
        p++;
        if (arr[hi] == arr[lo]) {                 /* guard: avoid division by zero */
            *probes = p;
            return lo;                            /* target must equal arr[lo] here */
        }
        /* widen to long long: target-arr[lo] and arr[hi]-arr[lo] can overflow a 32-bit int
           when the array spans values near INT_MIN and INT_MAX at once */
        long long span = (long long) arr[hi] - (long long) arr[lo];
        long long num = (long long) target - (long long) arr[lo];
        int pos = lo + (int) ((double) num * (hi - lo) / (double) span);
        if (arr[pos] == target) { *probes = p; return pos; }
        if (arr[pos] < target) lo = pos + 1;
        else hi = pos - 1;
    }
    *probes = p;
    return -1;
}

static int interpolationSearch(int[] arr, int target) {
    int lo = 0, hi = arr.length - 1;
    probes = 0;
    while (lo <= hi && target >= arr[lo] && target <= arr[hi]) {
        probes++;
        if (arr[hi] == arr[lo]) {                 // guard: avoid division by zero
            return lo;                            // target must equal arr[lo] here
        }
        // widen to long: target-arr[lo] and arr[hi]-arr[lo] can overflow a 32-bit int
        // when the array spans values near Integer.MIN_VALUE and Integer.MAX_VALUE at once
        long span = (long) arr[hi] - (long) arr[lo];
        long num = (long) target - (long) arr[lo];
        int pos = lo + (int) ((double) num * (hi - lo) / (double) span);
        if (arr[pos] == target) return pos;
        if (arr[pos] < target) lo = pos + 1;
        else hi = pos - 1;
    }
    return -1;
}

Oynatıcıda ayrıca şunları da deneyin: hafif düzensiz aralıklar, birkaç yoklama gerekir (zor) ve uç durumlar çarpık veri: son değer çok büyük, çok sayıda yoklama, tüm değerler eşit: bölme koruması devreye girer, ve hedef aralığın tamamen dışında: tek bakışta reddedilir — ya da rastgele veri için 🎲'ye basın, ya da kendi sıralı dizinizi yazın.

3.5 Dene¶

/* Week 6 -- Search and Hashing
 * Interpolation search: on a SORTED, roughly uniform array, estimate where
 * the target should be with a formula instead of always checking the
 * middle. A guard avoids dividing by zero when the current range is all one
 * value. Prints every probe.
 * CEN207 Data Structures (formerly CE205)
 */
#include <stdio.h>

int interpolation_search(const int arr[], int n, int target, int *probes) {
    int lo = 0, hi = n - 1, p = 0;
    while (lo <= hi && target >= arr[lo] && target <= arr[hi]) {
        p++;
        if (arr[hi] == arr[lo]) {                 /* guard: avoid division by zero */
            printf("  probe %d: arr[hi] == arr[lo] (%d), guard triggered\n", p, arr[lo]);
            *probes = p;
            return lo;                            /* target must equal arr[lo] here */
        }
        /* widen to long long: target-arr[lo] and arr[hi]-arr[lo] can overflow a 32-bit int
           when the array spans values near INT_MIN and INT_MAX at once */
        long long span = (long long) arr[hi] - (long long) arr[lo];
        long long num = (long long) target - (long long) arr[lo];
        int pos = lo + (int) ((double) num * (hi - lo) / (double) span);
        printf("  probe %d: lo=%d hi=%d pos=%d arr[pos]=%d\n", p, lo, hi, pos, arr[pos]);
        if (arr[pos] == target) { *probes = p; return pos; }
        if (arr[pos] < target) lo = pos + 1;
        else hi = pos - 1;
    }
    *probes = p;
    return -1;
}

static void print_array(const int arr[], int n) {
    printf("arr =");
    for (int i = 0; i < n; i++) printf(" %d", arr[i]);
    printf("\n");
}

static void run_scenario(const char *label, const int arr[], int n, int target) {
    printf("-- %s --\n", label);
    print_array(arr, n);
    printf("target = %d\n", target);
    int probes = 0;
    int index = interpolation_search(arr, n, target, &probes);
    if (index == -1) printf("result: not found, %d probes\n\n", probes);
    else printf("result: found at index %d, %d probes\n\n", index, probes);
}

int main(void) {
    int normal[] = {10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85};
    int hard[] = {10, 13, 21, 24, 33, 36, 44, 48, 55, 61, 68, 74, 81, 87, 94, 100};
    int skewed[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 1000000};
    int all_equal[] = {42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42};

    run_scenario("normal: uniformly spread 16 values, found in a single probe", normal, 16, 55);
    run_scenario("hard: slightly uneven spacing, needs a few probes", hard, 16, 81);
    run_scenario("edge: skewed data, last value is huge, many probes", skewed, 16, 8);
    run_scenario("edge: all values equal, the division guard kicks in", all_equal, 16, 42);
    run_scenario("edge: target is entirely outside the range, rejected on sight", normal, 16, 999);

    return 0;
}

/* Week 6 -- Search and Hashing
 * Interpolation search: on a SORTED, roughly uniform array, estimate where
 * the target should be with a formula instead of always checking the
 * middle. A guard avoids dividing by zero when the current range is all one
 * value. Prints every probe.
 * CEN207 Data Structures (formerly CE205)
 */
public class InterpolationSearch {
    static int probes;

    static int interpolationSearch(int[] arr, int target) {
        int lo = 0, hi = arr.length - 1;
        probes = 0;
        while (lo <= hi && target >= arr[lo] && target <= arr[hi]) {
            probes++;
            if (arr[hi] == arr[lo]) {                 // guard: avoid division by zero
                System.out.println("  probe " + probes + ": arr[hi] == arr[lo] (" + arr[lo] + "), guard triggered");
                return lo;                            // target must equal arr[lo] here
            }
            // widen to long: target-arr[lo] and arr[hi]-arr[lo] can overflow a 32-bit int
            // when the array spans values near Integer.MIN_VALUE and Integer.MAX_VALUE at once
            long span = (long) arr[hi] - (long) arr[lo];
            long num = (long) target - (long) arr[lo];
            int pos = lo + (int) ((double) num * (hi - lo) / (double) span);
            System.out.println("  probe " + probes + ": lo=" + lo + " hi=" + hi + " pos=" + pos + " arr[pos]=" + arr[pos]);
            if (arr[pos] == target) return pos;
            if (arr[pos] < target) lo = pos + 1;
            else hi = pos - 1;
        }
        return -1;
    }

    static void printArray(int[] arr) {
        StringBuilder sb = new StringBuilder("arr =");
        for (int v : arr) sb.append(' ').append(v);
        System.out.println(sb);
    }

    static void runScenario(String label, int[] arr, int target) {
        System.out.println("-- " + label + " --");
        printArray(arr);
        System.out.println("target = " + target);
        int index = interpolationSearch(arr, target);
        if (index == -1) System.out.println("result: not found, " + probes + " probes");
        else System.out.println("result: found at index " + index + ", " + probes + " probes");
        System.out.println();
    }

    public static void main(String[] args) {
        int[] normal = {10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85};
        int[] hard = {10, 13, 21, 24, 33, 36, 44, 48, 55, 61, 68, 74, 81, 87, 94, 100};
        int[] skewed = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 1000000};
        int[] allEqual = {42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42};

        runScenario("normal: uniformly spread 16 values, found in a single probe", normal, 55);
        runScenario("hard: slightly uneven spacing, needs a few probes", hard, 81);
        runScenario("edge: skewed data, last value is huge, many probes", skewed, 8);
        runScenario("edge: all values equal, the division guard kicks in", allEqual, 42);
        runScenario("edge: target is entirely outside the range, rejected on sight", normal, 999);
    }
}

Dene

gcc -std=c11 -Wall -Wextra -o /tmp/x interpolation_search.c && /tmp/x

-- normal: uniformly spread 16 values, found in a single probe --
arr = 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85
target = 55
  probe 1: lo=0 hi=15 pos=9 arr[pos]=55
result: found at index 9, 1 probes

-- hard: slightly uneven spacing, needs a few probes --
arr = 10 13 21 24 33 36 44 48 55 61 68 74 81 87 94 100
target = 81
  probe 1: lo=0 hi=15 pos=11 arr[pos]=74
  probe 2: lo=12 hi=15 pos=12 arr[pos]=81
result: found at index 12, 2 probes

-- edge: skewed data, last value is huge, many probes --
arr = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1000000
target = 8
  probe 1: lo=0 hi=15 pos=0 arr[pos]=1
  probe 2: lo=1 hi=15 pos=1 arr[pos]=2
  probe 3: lo=2 hi=15 pos=2 arr[pos]=3
  probe 4: lo=3 hi=15 pos=3 arr[pos]=4
  probe 5: lo=4 hi=15 pos=4 arr[pos]=5
  probe 6: lo=5 hi=15 pos=5 arr[pos]=6
  probe 7: lo=6 hi=15 pos=6 arr[pos]=7
  probe 8: lo=7 hi=15 pos=7 arr[pos]=8
result: found at index 7, 8 probes

-- edge: all values equal, the division guard kicks in --
arr = 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42
target = 42
  probe 1: arr[hi] == arr[lo] (42), guard triggered
result: found at index 0, 1 probes

-- edge: target is entirely outside the range, rejected on sight --
arr = 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85
target = 999
result: not found, 0 probes

javac -Xlint:all -d /tmp/j InterpolationSearch.java && java -cp /tmp/j InterpolationSearch

3.6 Karmaşıklık, hatalar, kendini sına¶

Karmaşıklık. Tek düze dağılmış veride ortalama durum O(log log n); çarpık veride en kötü durum O(n) (yukarıdaki [1, 2, 3, ..., 15, 1000000] dizisi, yalnızca 16 eleman için 8 yoklama gerektirdi — aynı şeklin bir milyon elemana ölçeklendiğini hayal edin). İkili arama gibi tam olarak sıralı bir dizi gerektirir.

4. Üstel arama (exponential search)¶

4.1 Başlangıç sorusu¶

İkili arama, ilk orta noktayı hesaplamak için başlamadan önce dizinin boyutunu, n'i, bilmek zorundadır. Peki ya dizi etkili biçimde sınırsızsa — sıralı bir akış, ya da yalnızca n'i okumanın bile pahalı olduğu kadar devasa bir dizi — ve hedefin, varsa, başa yakın bir yerde olduğundan güçlü şekilde şüpheleniyorsanız? Önce n'i bulmak için tamamını taramak israf olurdu. Üstel arama (exponential search) bunu çözer: hedefi kapsadığı garanti edilen bir sınır (bound) bulun, ikiye katlayarak (1, 2, 4, 8, …) onu aşana kadar, sonra o sınırın içinde sıradan ikili arama çalıştırın. Sınır bulma aşaması yalnızca O(log index)'e mal olur — hedefin gerçekte ne kadar ileride olduğuyla orantılı — O(log n)'e değil.

Jon Bentley ve Andrew Yao bu tekniği, 1976 tarihli An Almost Optimal Algorithm for Unbounded Searching (Information Processing Letters) makalelerinde yayımladı. Sınırsız arama (unbounded search) ya da dörtnala arama (galloping search) olarak da anılır — "dörtnala", sınır bulma aşamasının küçükten büyüğe büyüyen adımları için canlı bir benzetmedir, tıpkı hızlanan bir atın adımları gibi — ve bugün birçok birleştirme (merge) ve küme-kesişimi algoritmasının içinde kullanılır.

4.2 Fikir: aşana kadar ikiye katla, sonra ikili arama yap¶

Önce arr[0]'ı kontrol edin (karşılaştırma #1). Hedef değilse, bound'u ikiye katlayarak büyütün — 1, 2, 4, 8, … — her seferinde arr[bound]'u kontrol ederek, arr[bound] >= target olana ya da bound >= n olana kadar. O noktada, target, varsa, [bound/2, min(bound, n-1)] içinde olmalıdır — çünkü önceki, daha küçük sınır kontrol edilmiş ve < target bulunmuştur. Sıradan ikili aramayı tam olarak o aralığın içinde çalıştırın.

4.3 Bellekte nasıl durur, ve kod¶

int exponential_search(const int arr[], int n, int target, int *comparisons) {
    if (n <= 0) { *comparisons = 0; return -1; }    /* nothing to search */
    int comp = 1;                    /* the arr[0] check below counts as comparison #1 */
    if (arr[0] == target) { *comparisons = comp; return 0; }
    int bound = 1;
    while (bound < n) {                 /* double the bound until it overshoots target */
        comp++;
        if (arr[bound] >= target) break;
        bound *= 2;
    }
    int lo = bound / 2, hi = (bound < n) ? bound : n - 1;
    while (lo <= hi) {                  /* ordinary binary search inside [lo..hi] */
        int mid = lo + (hi - lo) / 2;
        comp++;
        if (arr[mid] == target) { *comparisons = comp; return mid; }
        if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    *comparisons = comp;
    return -1;
}

static int exponentialSearch(int[] arr, int target) {
    int n = arr.length;
    if (n <= 0) { comparisons = 0; return -1; }  // nothing to search
    comparisons = 1;                 // the arr[0] check below counts as comparison #1
    if (arr[0] == target) return 0;
    int bound = 1;
    while (bound < n) {                 // double the bound until it overshoots target
        comparisons++;
        if (arr[bound] >= target) break;
        bound *= 2;
    }
    int lo = bound / 2, hi = (bound < n) ? bound : n - 1;
    while (lo <= hi) {                  // ordinary binary search inside [lo..hi]
        int mid = lo + (hi - lo) / 2;
        comparisons++;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

Oynatıcıda ayrıca şunları da deneyin: hedef sona yakın, sınır birkaç kez ikiye katlanır (zor) ve uç durumlar hedef ilk elemanda: tek karşılaştırma, hedef son elemandan da büyük, ve hedef aralıkta ama dizide yok — ya da rastgele veri için 🎲'ye basın, ya da kendi sıralı dizinizi yazın.

4.4 Dene¶

/* Week 6 -- Search and Hashing
 * Exponential search: on a SORTED array, double a bound (1, 2, 4, 8, ...)
 * until it overshoots target, then run ordinary binary search inside
 * [bound/2, bound]. Prints the bound-finding phase and the binary-search
 * phase.
 * CEN207 Data Structures (formerly CE205)
 */
#include <stdio.h>

int exponential_search(const int arr[], int n, int target, int *comparisons) {
    if (n <= 0) { *comparisons = 0; return -1; }    /* nothing to search */
    int comp = 1;                    /* the arr[0] check below counts as comparison #1 */
    printf("  check arr[0] = %d\n", arr[0]);
    if (arr[0] == target) { *comparisons = comp; return 0; }
    int bound = 1;
    while (bound < n) {                 /* double the bound until it overshoots target */
        comp++;
        printf("  bound = %d: check arr[%d] = %d\n", bound, bound, arr[bound]);
        if (arr[bound] >= target) break;
        bound *= 2;
    }
    int lo = bound / 2, hi = (bound < n) ? bound : n - 1;
    printf("  binary search inside [%d..%d]\n", lo, hi);
    while (lo <= hi) {                  /* ordinary binary search inside [lo..hi] */
        int mid = lo + (hi - lo) / 2;
        comp++;
        printf("  compare arr[%d] = %d\n", mid, arr[mid]);
        if (arr[mid] == target) { *comparisons = comp; return mid; }
        if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    *comparisons = comp;
    return -1;
}

static void print_array(const int arr[], int n) {
    printf("arr =");
    for (int i = 0; i < n; i++) printf(" %d", arr[i]);
    printf("\n");
}

static void run_scenario(const char *label, const int arr[], int n, int target) {
    printf("-- %s --\n", label);
    print_array(arr, n);
    printf("target = %d\n", target);
    int comparisons = 0;
    int index = exponential_search(arr, n, target, &comparisons);
    if (index == -1) printf("result: not found, %d comparisons\n\n", comparisons);
    else printf("result: found at index %d, %d comparisons\n\n", index, comparisons);
}

int main(void) {
    int a[] = {3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 55, 59, 63};
    int n = 16;

    run_scenario("normal: 16 values, target found around the middle", a, n, 39);
    run_scenario("hard: target near the end, the bound doubles several times", a, n, 59);
    run_scenario("edge: target is the first element, a single comparison", a, n, 3);
    run_scenario("edge: target is larger than the last element", a, n, 999);
    run_scenario("edge: target is in range but not in the array", a, n, 40);

    return 0;
}

/* Week 6 -- Search and Hashing
 * Exponential search: on a SORTED array, double a bound (1, 2, 4, 8, ...)
 * until it overshoots target, then run ordinary binary search inside
 * [bound/2, bound]. Prints the bound-finding phase and the binary-search
 * phase.
 * CEN207 Data Structures (formerly CE205)
 */
public class ExponentialSearch {
    static int comparisons;

    static int exponentialSearch(int[] arr, int target) {
        int n = arr.length;
        if (n <= 0) { comparisons = 0; return -1; }  // nothing to search
        comparisons = 1;                 // the arr[0] check below counts as comparison #1
        System.out.println("  check arr[0] = " + arr[0]);
        if (arr[0] == target) return 0;
        int bound = 1;
        while (bound < n) {                 // double the bound until it overshoots target
            comparisons++;
            System.out.println("  bound = " + bound + ": check arr[" + bound + "] = " + arr[bound]);
            if (arr[bound] >= target) break;
            bound *= 2;
        }
        int lo = bound / 2, hi = (bound < n) ? bound : n - 1;
        System.out.println("  binary search inside [" + lo + ".." + hi + "]");
        while (lo <= hi) {                  // ordinary binary search inside [lo..hi]
            int mid = lo + (hi - lo) / 2;
            comparisons++;
            System.out.println("  compare arr[" + mid + "] = " + arr[mid]);
            if (arr[mid] == target) return mid;
            if (arr[mid] < target) lo = mid + 1;
            else hi = mid - 1;
        }
        return -1;
    }

    static void printArray(int[] arr) {
        StringBuilder sb = new StringBuilder("arr =");
        for (int v : arr) sb.append(' ').append(v);
        System.out.println(sb);
    }

    static void runScenario(String label, int[] arr, int target) {
        System.out.println("-- " + label + " --");
        printArray(arr);
        System.out.println("target = " + target);
        int index = exponentialSearch(arr, target);
        if (index == -1) System.out.println("result: not found, " + comparisons + " comparisons");
        else System.out.println("result: found at index " + index + ", " + comparisons + " comparisons");
        System.out.println();
    }

    public static void main(String[] args) {
        int[] a = {3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 55, 59, 63};

        runScenario("normal: 16 values, target found around the middle", a, 39);
        runScenario("hard: target near the end, the bound doubles several times", a, 59);
        runScenario("edge: target is the first element, a single comparison", a, 3);
        runScenario("edge: target is larger than the last element", a, 999);
        runScenario("edge: target is in range but not in the array", a, 40);
    }
}

Dene

gcc -std=c11 -Wall -Wextra -o /tmp/x exponential_search.c && /tmp/x

-- normal: 16 values, target found around the middle --
arr = 3 7 11 15 19 23 27 31 35 39 43 47 51 55 59 63
target = 39
  check arr[0] = 3
  bound = 1: check arr[1] = 7
  bound = 2: check arr[2] = 11
  bound = 4: check arr[4] = 19
  bound = 8: check arr[8] = 35
  binary search inside [8..15]
  compare arr[11] = 47
  compare arr[9] = 39
result: found at index 9, 7 comparisons

-- hard: target near the end, the bound doubles several times --
arr = 3 7 11 15 19 23 27 31 35 39 43 47 51 55 59 63
target = 59
  check arr[0] = 3
  bound = 1: check arr[1] = 7
  bound = 2: check arr[2] = 11
  bound = 4: check arr[4] = 19
  bound = 8: check arr[8] = 35
  binary search inside [8..15]
  compare arr[11] = 47
  compare arr[13] = 55
  compare arr[14] = 59
result: found at index 14, 8 comparisons

-- edge: target is the first element, a single comparison --
arr = 3 7 11 15 19 23 27 31 35 39 43 47 51 55 59 63
target = 3
  check arr[0] = 3
result: found at index 0, 1 comparisons

-- edge: target is larger than the last element --
arr = 3 7 11 15 19 23 27 31 35 39 43 47 51 55 59 63
target = 999
  check arr[0] = 3
  bound = 1: check arr[1] = 7
  bound = 2: check arr[2] = 11
  bound = 4: check arr[4] = 19
  bound = 8: check arr[8] = 35
  binary search inside [8..15]
  compare arr[11] = 47
  compare arr[13] = 55
  compare arr[14] = 59
  compare arr[15] = 63
result: not found, 9 comparisons

-- edge: target is in range but not in the array --
arr = 3 7 11 15 19 23 27 31 35 39 43 47 51 55 59 63
target = 40
  check arr[0] = 3
  bound = 1: check arr[1] = 7
  bound = 2: check arr[2] = 11
  bound = 4: check arr[4] = 19
  bound = 8: check arr[8] = 35
  binary search inside [8..15]
  compare arr[11] = 47
  compare arr[9] = 39
  compare arr[10] = 43
result: not found, 8 comparisons

javac -Xlint:all -d /tmp/j ExponentialSearch.java && java -cp /tmp/j ExponentialSearch

4.5 Karmaşıklık, hatalar, kendini sına¶

Karmaşıklık. Sınırı bulmak için O(log index), burada index hedefin gerçek konumudur (yoksa n) — O(log n) değil. İkili arama aşaması sonra O(log(bound))'a mal olur, burada bound en fazla 2 * index'tir. Birleşik: genel olarak O(log index). Hedef başa yakınken, bu düz ikili aramanın O(log n)'inden daha iyidir; hedef sona yakınken, ikisi asimptotik olarak aynı olur.

5. Fibonacci araması (Fibonacci search)¶

5.1 Başlangıç sorusu¶

İkili aramanın orta nokta hesabı, lo + (hi - lo) / 2, bir bölme gerektirir. 1950'lerin ve 1960'ların bilgisayar donanımında — ve bugün bile bazı çok kısıtlı gömülü (embedded) işlemcilerde — bölme, toplama ya da çıkarmadan çarpıcı biçimde daha pahalıdır. İkili aramanın O(log n) garantisini yalnızca toplama ve çıkarma kullanarak elde etmenin bir yolu var mı? Fibonacci araması, aralığı her zaman tam ortadan bölmek yerine Fibonacci sayılarına (1, 1, 2, 3, 5, 8, 13, 21, …) göre bölerek "evet" der.

Teknik, Amerikalı istatistikçi Jack Kiefer'ın çalışmasına dayanır; onun 1953 tarihli Sequential Minimax Search for a Maximum makalesi, ilişkili bir problem için (bir fonksiyonun maksimumunu, mümkün olduğunca az değerlendirmeyle bulmak) en uygun bir strateji tasarlamak amacıyla Fibonacci sayılarını kullandı; aynı Fibonacci-sayısı-bölme fikri, daha sonra sıralı diziler için bölmesiz bir arama algoritmasına uyarlandı — burada öğrendiğiniz de tam olarak budur.

5.2 Fikir¶

n'e >= olan en küçük Fibonacci sayısını, fib'i, ondan hemen önceki iki Fibonacci sayısıyla birlikte bulun, fib1 ve fib2 (yani fib = fib1 + fib2). Aramanın diziye ne kadar ilerlediğini işaretleyen bir offset (başlangıçta -1) tutun. Her adımda, indeks i = offset + fib2'yi yoklayın (aşarsa n - 1'e sabitlenir). arr[i] < target ise, i'ye kadar olan sol kısmın tamamı elenir, offset i'ye taşınır, ve Fibonacci üçlüsü bir adım küçülür (fib, fib1, fib2 = fib1, fib2, fib1 - fib2). arr[i] > target ise, sağ kısım elenir, ve üçlü iki adım küçülür (fib, fib1, fib2 = fib2, fib1 - fib2, fib - (fib1 - fib2)). Fibonacci sayıları fib = fib1 + fib2'yi tam olarak sağladığından, bu güncellemelerin her biri yalnızca toplama ve çıkarma kullanır — asla bölme ya da çarpma değil.

5.3 Bellekte nasıl durur, ve kod¶

int fibonacci_search(const int arr[], int n, int target, int *comparisons) {
    int fib2 = 0, fib1 = 1, fib = fib1 + fib2;      /* smallest Fibonacci number >= n */
    while (fib < n) { fib2 = fib1; fib1 = fib; fib = fib1 + fib2; }
    int offset = -1, comp = 0;
    while (fib > 1) {
        int i = (offset + fib2 < n - 1) ? offset + fib2 : n - 1;
        comp++;
        if (arr[i] < target) {                       /* eliminate the left part */
            fib = fib1; fib1 = fib2; fib2 = fib - fib1;
            offset = i;
        } else if (arr[i] > target) {                /* eliminate the right part */
            fib = fib2; fib1 = fib1 - fib2; fib2 = fib - fib1;
        } else {
            *comparisons = comp;
            return i;
        }
    }
    if (fib1 == 1 && offset + 1 < n) {                /* one element may be left over */
        comp++;
        if (arr[offset + 1] == target) { *comparisons = comp; return offset + 1; }
    }
    *comparisons = comp;
    return -1;
}

static int fibonacciSearch(int[] arr, int target) {
    int n = arr.length;
    int fib2 = 0, fib1 = 1, fib = fib1 + fib2;      // smallest Fibonacci number >= n
    while (fib < n) { fib2 = fib1; fib1 = fib; fib = fib1 + fib2; }
    int offset = -1;
    comparisons = 0;
    while (fib > 1) {
        int i = (offset + fib2 < n - 1) ? offset + fib2 : n - 1;
        comparisons++;
        if (arr[i] < target) {                       // eliminate the left part
            fib = fib1; fib1 = fib2; fib2 = fib - fib1;
            offset = i;
        } else if (arr[i] > target) {                // eliminate the right part
            fib = fib2; fib1 = fib1 - fib2; fib2 = fib - fib1;
        } else {
            return i;
        }
    }
    if (fib1 == 1 && offset + 1 < n) {                // one element may be left over
        comparisons++;
        if (arr[offset + 1] == target) return offset + 1;
    }
    return -1;
}