Data terurut memberi keuntungan lebih dari sekadar memungkinkan binary search. Kita bisa memanfaatkan struktur terurut untuk algoritma pencarian khusus yang unggul dalam skenario tertentu: jump search menggabungkan keunggulan cache linear dengan kompleksitas logaritmik, exponential search cepat untuk pencarian dekat awal array, dan interpolation search secara dramatis lebih cepat bila data terdistribusi seragam. Pada Chapter ini kita akan mempelajari tiga algoritma tersebut, kapan masing-masing unggul, serta perbandingannya secara empiris.

Aturan dan Mekanisme #

Jump search melompat maju dengan langkah tetap √n, lalu setelah melewati target, melakukan linear search mundur pada blok terakhir yang dilewati.

  1. Pilih ukuran langkah step = floor(√n).
  2. Lompat maju hingga a[min(step, n) - 1] ≥ target atau mencapai akhir.
  3. Linear search pada blok sebelum posisi lompatan saat ini.

Kompleksitas: O(√n). Lebih baik dari linear search O(n), tetapi lebih buruk dari binary search O(log n). Keunggulan utama: lebih cache-friendly karena akses maju sekuensial dalam blok.

cpp 
#include <iostream>
#include <vector>
#include <cmath>
#include <optional>

std::optional<size_t> jump_search(const std::vector<int>& a, int target) {
    size_t n = a.size();
    if (n == 0) return std::nullopt;
    size_t step = static_cast<size_t>(std::sqrt(n));
    size_t prev = 0;

    // Lompat maju hingga a[min(step, n) - 1] >= target
    while (prev < n && a[std::min(step, n) - 1] < target) {
        prev = step;
        step += static_cast<size_t>(std::sqrt(n));
        if (prev >= n) return std::nullopt;
    }

    // Linear search pada blok [prev, min(step, n))
    size_t end = std::min(step, n);
    for (size_t i = prev; i < end; ++i) {
        if (a[i] == target) return i;
        if (a[i] > target)  break;  // pasti tidak ada
    }
    return std::nullopt;
}

int main() {
    std::vector<int> a = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21};
    for (int t : {13, 4, 1, 21, 22}) {
        auto r = jump_search(a, t);
        std::cout << "cari " << t << ": ";
        if (r) std::cout << "indeks " << *r << '\n';
        else    std::cout << "tidak ketemu\n";
    }
    return 0;
}

Output yang Dihasilkan:

text 
cari 13: indeks 6
cari 4: tidak ketemu
cari 1: indeks 0
cari 21: indeks 10
cari 22: tidak ketemu
  1. Baris size_t step = static_cast<size_t>(std::sqrt(n));: langkah optimal adalah √n. Meminimalkan total operasi n/step + step - 1 = 2√n - 1 saat step = √n.
  2. Baris while (a[min(step, n) - 1] < target): lompat maju sekuensial. Cache-friendly karena akses memori berurutan.
  3. Baris if (prev >= n) return std::nullopt;: bila lompatan melewati akhir, target pasti tidak ada.
  4. Baris if (a[i] > target) break;: optimasi early-exit dalam linear search. Karena array terurut, bila elemen saat ini sudah melebihi target, target pasti tidak ada.
  5. Kompleksitas: O(√n) — lompatan √n kali, linear search √n elemen.

Aturan dan Mekanisme #

Exponential search (juga disebut galloping search) memulai dari indeks 0 dan menggandakan jangkauan hingga menemukan batas atas untuk target, lalu binary search pada rentang tersebut.

  1. Bila a[0] == target, kembalikan 0.
  2. Mulai dari i = 1; gandakan i hingga a[i] ≥ target atau i ≥ n.
  3. Binary search pada [i/2, min(i, n-1)].

Kompleksitas: O(log n). Keunggulan utama: sangat efisien bila target berada dekat awal array (hanya butuh sedikit penggandaan). Cocok untuk array tak terbatas atau stream.

cpp 
#include <iostream>
#include <vector>
#include <algorithm>
#include <optional>

std::optional<size_t> exponential_search(const std::vector<int>& a, int target) {
    if (a.empty()) return std::nullopt;
    if (a[0] == target) return 0;

    size_t i = 1;
    while (i < a.size() && a[i] <= target) i *= 2;

    // Binary search pada [i/2, min(i, n-1)]
    size_t lo = i / 2;
    size_t hi = std::min(i, a.size() - 1);
    while (lo <= hi) {
        size_t mid = lo + (hi - lo) / 2;
        if (a[mid] == target) return mid;
        else if (a[mid] < target) lo = mid + 1;
        else                       hi = mid - 1;
    }
    return std::nullopt;
}

int main() {
    std::vector<int> a = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30};
    for (int t : {2, 18, 30, 7}) {
        auto r = exponential_search(a, t);
        std::cout << "cari " << t << ": ";
        if (r) std::cout << "indeks " << *r << '\n';
        else    std::cout << "tidak ketemu\n";
    }
    return 0;
}

Output yang Dihasilkan:

text 
cari 2: indeks 0
cari 18: indeks 8
cari 30: indeks 14
cari 7: tidak ketemu
  1. Baris if (a[0] == target) return 0;: kasus khusus untuk indeks 0.
  2. Baris while (i < a.size() && a[i] <= target) i *= 2;: penggandaan eksponensial — 1, 2, 4, 8, 16, … hingga menemukan batas.
  3. Baris size_t lo = i / 2;: batas bawah yang pasti ≤ target.
  4. Baris size_t hi = std::min(i, a.size() - 1);: batas atas yang mungkin ≥ target atau akhir array.
  5. Binary search: O(log n) tahap kedua.
  6. Total: O(log posisi target) — bila target di indeks k, eksponensial butuh O(log k) lompatan, binary search O(log(min(i, n) - i/2)) = O(log i) = O(log k).

Aturan dan Mekanisme #

Interpolation search memperkirakan posisi target dengan asumsi data terdistribusi seragam. Alih-alih selalu mengambil titik tengah, algoritma menghitung posisi probabilitas berdasarkan nilai.

  1. Estimasi posisi: pos = lo + (target - a[lo]) * (hi - lo) / (a[hi] - a[lo]).
  2. Bila a[pos] == target, kembalikan.
  3. Bila a[pos] < target, cari di kanan. Bila > target, cari di kiri.

Kompleksitas rata-rata: O(log log n) bila data seragam. Worst case: O(n) bila data tidak seragam.

cpp 
#include <iostream>
#include <vector>
#include <optional>

std::optional<size_t> interpolation_search(const std::vector<int>& a, int target) {
    if (a.empty()) return std::nullopt;
    size_t lo = 0;
    size_t hi = a.size() - 1;

    while (lo <= hi && target >= a[lo] && target <= a[hi]) {
        if (lo == hi) {
            if (a[lo] == target) return lo;
            return std::nullopt;
        }
        // Estimasi posisi
        size_t pos = lo + static_cast<size_t>(
            (static_cast<long long>(target - a[lo]) *
             static_cast<long long>(hi - lo)) /
            static_cast<long long>(a[hi] - a[lo]));

        if (pos >= a.size()) break;
        if (a[pos] == target) return pos;
        else if (a[pos] < target) lo = pos + 1;
        else                       hi = pos - 1;
    }
    return std::nullopt;
}

int main() {
    std::vector<int> a;
    for (int i = 0; i < 100; ++i) a.push_back(i * 10);  // 0, 10, 20, ..., 990

    for (int t : {0, 100, 500, 990, 995}) {
        auto r = interpolation_search(a, t);
        std::cout << "cari " << t << ": ";
        if (r) std::cout << "indeks " << *r << '\n';
        else    std::cout << "tidak ketemu\n";
    }
    return 0;
}

Output yang Dihasilkan:

text 
cari 0: indeks 0
cari 100: indeks 10
cari 500: indeks 50
cari 990: indeks 99
cari 995: tidak ketemu
  1. Baris while (... target >= a[lo] && target <= a[hi]): target harus berada dalam rentang nilai array. Bila di luar, pasti tidak ada.
  2. Baris size_t pos = lo + ...: rumus interpolasi linier. Estimasi posisi berdasarkan proporsi nilai target dalam rentang [a[lo], a[hi]].
  3. Konversi long long: menghindari overflow saat target - a[lo] dan hi - lo dikalikan.
  4. Hasil: pada data seragam (0, 10, 20, …, 990), interpolation search menemukan target dalam 1-2 iterasi — jauh lebih cepat dari binary search.
  5. Kompleksitas rata-rata: O(log log n) untuk distribusi seragam.

Perbandingan Empiris #

Mari kita uji kompleksitas keempat algoritma pada array besar dengan target di akhir.

Kode: Benchmark Empiris #

cpp 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>

long long g_count = 0;  // penghitung komparasi

size_t binary_search_cnt(const std::vector<int>& a, int t) {
    size_t lo = 0, hi = a.size() - 1;
    while (lo <= hi) {
        ++g_count;
        size_t mid = lo + (hi - lo) / 2;
        if (a[mid] == t) return mid;
        else if (a[mid] < t) lo = mid + 1;
        else                  hi = mid - 1;
    }
    return a.size();
}

size_t jump_search_cnt(const std::vector<int>& a, int t) {
    size_t n = a.size();
    size_t step = static_cast<size_t>(std::sqrt(n));
    size_t prev = 0;
    while (prev < n && a[std::min(step, n) - 1] < t) {
        ++g_count;
        prev = step;
        step += static_cast<size_t>(std::sqrt(n));
        if (prev >= n) return n;
    }
    size_t end = std::min(step, n);
    for (size_t i = prev; i < end; ++i) {
        ++g_count;
        if (a[i] == t) return i;
        if (a[i] > t) break;
    }
    return n;
}

int main() {
    std::vector<int> a;
    for (int i = 0; i < 10000; ++i) a.push_back(i * 2);

    int target = a.back();  // target di akhir = worst case

    g_count = 0;
    binary_search_cnt(a, target);
    long long bs = g_count;

    g_count = 0;
    jump_search_cnt(a, target);
    long long js = g_count;

    std::cout << "n = 10000, target di akhir (worst case)\n";
    std::cout << "binary search : " << bs << " komparasi (log2(10000) ~ "
              << log2(10000) << ")\n";
    std::cout << "jump search   : " << js << " komparasi (2*sqrt(10000) ~ "
              << 2 * sqrt(10000) << ")\n";
    return 0;
}

Output yang Dihasilkan:

text 
n = 10000, target di akhir (worst case)
binary search : 14 komparasi (log2(10000) ~ 13.2877)
jump search   : 199 komparasi (2*sqrt(10000) ~ 200)
  1. Binary search 14 komparasi: sesuai dengan ceil(log2(10000)) = 14. Worst case binary search jauh lebih efisien daripada jump search.
  2. Jump search 199 komparasi: sesuai dengan rumus 2√n - 1 ≈ 199 untuk n = 10000. Memang lebih banyak komparasi, tetapi akses memori berurutan membuatnya cache-friendly.
  3. Trade-off: untuk data besar, binary search menang dalam jumlah komparasi; jump search menang dalam cache locality (terutama bila data tidak muat di cache L1/L2).

Kapan Memilih Algoritma Mana #

SkenarioAlgoritmaAlasan
Data terurut, distribusi tidak diketahuiBinary searchKonsisten O(log n) tanpa asumsi
Data terurut, target dekat awalExponential searchKonvergensi cepat untuk posisi kecil
Data tak terbatas / streamExponential searchTidak perlu tahu n di awal
Data terurut seragam (sensor, ID)Interpolation searchO(log log n) rata-rata
Data terurut, sangat besar, cache-miss mahalJump searchCache-friendly sekuensial
Data tidak terurut, n < 32Linear searchOverhead nol, pemenang praktis

Ringkasan #

  • Jump search: langkah √n, kompleksitas O(√n), cache-friendly. Untuk data besar dengan cache-miss mahal.
  • Exponential search: penggandaan 2^k, kompleksitas O(log n), ideal untuk target dekat awal atau array tak terbatas.
  • Interpolation search: estimasi posisi berbasis nilai, rata-rata O(log log n) untuk data seragam, worst case O(n) untuk data clustered.
  • Pilihan algoritma bergantung pada karakteristik data: distribusi, ukuran, posisi target, dan cache behavior.
  • Untuk kasus umum, binary search tetap pilihan default — konsisten dan didukung STL.