Perbandingan Algoritma Searching

Sepanjang Section ini kita telah mempelajari enam algoritma searching: linear, binary, lower/upper bound, binary search on answer, ternary, jump, exponential, dan interpolation. Masing-masing memiliki prasyarat, kompleksitas, dan skenario terbaiknya sendiri. Memilih algoritma yang tepat menentukan apakah kode kita berjalan dalam 1 milidetik atau 1 detik. Pada Chapter ini kita akan merangkum perbandingan semua algoritma dalam satu tabel, membangun decision tree untuk pemilihan, lalu menguji secara empiris pada berbagai ukuran data.

Tabel Perbandingan Komprehensif #

Berikut ringkasan tujuh algoritma searching yang telah kita pelajari:

Algoritma	Prasyarat	Best	Average	Worst	Space
Linear search	Tidak ada	O(1)	O(n)	O(n)	O(1)
Binary search	Data terurut	O(1)	O(log n)	O(log n)	O(1)
Lower/upper bound	Data terurut	O(1)	O(log n)	O(log n)	O(1)
Binary search on answer	Predikat monoton	—	O(n log R)	O(n log R)	O(1)
Ternary search	Fungsi unimodal	O(1)	O(log_{1.5} n)	O(log_{1.5} n)	O(1)
Jump search	Data terurut	O(1)	O(√n)	O(√n)	O(1)
Exponential search	Data terurut	O(1)	O(log k)	O(log n)	O(1)
Interpolation search	Terurut + seragam	O(1)	O(log log n)	O(n)	O(1)

Decision Tree: Memilih Algoritma #

flowchart TD Start["Soal searching"] --> Q1{"Data terurut?"} Q1 -->|Tidak| Q2{"n kecil (< 32)?"} Q1 -->|Ya| Q3{"Distribusi seragam & n besar?"} Q2 -->|Ya| LS["Linear search"] Q2 -->|Tidak| Q2b{"n diketahui?"} Q2b -->|Ya| Sort["Sort + binary search O(n log n)"] Q2b -->|Tidak| Hash["Hash table O(n) build, O(1) query"] Q3 -->|Ya, target random| IS["Interpolation search"] Q3 -->|Tidak seragam| Q4{"Target dekat awal?"} Q4 -->|Ya| ES["Exponential search"] Q4 -->|Tidak| Q5{"Cari rentang elemen sama?"} Q5 -->|Ya| BB["lower_bound + upper_bound"] Q5 -->|Tidak| BS["Binary search"]

Pertanyaan Panduan Memilih #

Saat menghadapi soal searching, tanyakan diri sendiri pertanyaan berikut secara berurutan:

Apakah data terurut? Bila tidak, urutkan dulu (O(n log n)) atau gunakan hash table (O(n) build, O(1) query rata-rata).
Apakah target biasa atau elemen pertama/terakhir yang memenuhi kriteria? Untuk “elemen pertama ≥ v”, gunakan std::lower_bound. Untuk “elemen pertama > v”, gunakan std::upper_bound.
Apakah kita mencari optimum suatu fungsi alih-alih elemen array? Bila ya, kemungkinan besar ini binary search on answer.
Apakah fungsi yang dioptimasi unimodal? Bila ya, ternary search.
Apakah target biasanya dekat awal array? Exponential search menggabungkan keunggulan ini.
Apakah data terdistribusi seragam (sensor, ID berurutan)? Interpolation search menghasilkan O(log log n) rata-rata.
Apakah array sangat besar (> 10^6) dan tidak muat di cache? Jump search mungkin lebih cepat karena akses berurutan cache-friendly.

Benchmark Empiris: Lima Algoritma #

Mari kita uji lima algoritma pada array besar dengan berbagai posisi target.

Kode: Benchmark Lima Algoritma #

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

long long g_count = 0;

size_t linear(const std::vector<int>& a, int t) {
    for (size_t i = 0; i < a.size(); ++i) {
        ++g_count;
        if (a[i] == t) return i;
    }
    return a.size();
}

size_t binary(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(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;
}

size_t exponential(const std::vector<int>& a, int t) {
    if (a[0] == t) { ++g_count; return 0; }
    size_t i = 1;
    while (i < a.size() && a[i] <= t) { ++g_count; i *= 2; }
    size_t lo = i / 2, hi = std::min(i, 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 interpolation(const std::vector<int>& a, int t) {
    size_t lo = 0, hi = a.size() - 1;
    while (lo <= hi && t >= a[lo] && t <= a[hi]) {
        ++g_count;
        if (lo == hi) return a[lo] == t ? lo : a.size();
        size_t pos = lo + static_cast<size_t>(
            (static_cast<long long>(t - a[lo]) *
             static_cast<long long>(hi - lo)) /
            static_cast<long long>(a[hi] - a[lo]));
        if (pos >= a.size()) break;
        if (a[pos] == t) return pos;
        else if (a[pos] < t) lo = pos + 1;
        else                  hi = pos - 1;
    }
    return a.size();
}

void bench(const std::vector<int>& a, int t, const char* name,
           size_t(*f)(const std::vector<int>&, int))
{
    g_count = 0;
    f(a, t);
    std::cout << name << ": " << g_count << " komparasi\n";
}

int main() {
    std::vector<int> a;
    for (int i = 0; i < 100000; ++i) a.push_back(i * 2);  // n = 100000, seragam

    int target_mid = a[50000];      // target di tengah
    std::cout << "=== Target di tengah (indeks 50000) ===\n";
    bench(a, target_mid, "linear       ", linear);
    bench(a, target_mid, "binary       ", binary);
    bench(a, target_mid, "jump         ", jump);
    bench(a, target_mid, "exponential  ", exponential);
    bench(a, target_mid, "interpolation", interpolation);

    int target_near = a[5];  // target dekat awal
    std::cout << "\n=== Target dekat awal (indeks 5) ===\n";
    bench(a, target_near, "linear       ", linear);
    bench(a, target_near, "binary       ", binary);
    bench(a, target_near, "jump         ", jump);
    bench(a, target_near, "exponential  ", exponential);
    bench(a, target_near, "interpolation", interpolation);
    return 0;
}

Output yang Dihasilkan:

text
=== Target di tengah (indeks 50000) ===
linear       : 50001 komparasi
binary       : 16 komparasi
jump         : 231 komparasi
exponential  : 27 komparasi
interpolation: 1 komparasi

=== Target dekat awal (indeks 5) ===
linear       : 6 komparasi
binary       : 14 komparasi
jump         : 6 komparasi
exponential  : 6 komparasi
interpolation: 1 komparasi

Target di tengah: interpolation search menang telak dengan 1 komparasi (data seragam, estimasi langsung tepat), exponential search butuh 27 (log posisi + binary search), binary search 16 (log total), jump 231 (lompat + linear).
Target dekat awal: linear search menang bersama jump dan exponential dengan 6 komparasi (early exit tepat di target). Interpolation tetap efisien dengan 1 komparasi.
Binary search konsisten: 14-16 komparasi untuk n = 100000 tergantung posisi target. Inilah keunggulan utamanya — prediktabilitas.
Trade-off jelas: algoritma cepat pada satu skenario bisa lambat di skenario lain. Pemilihan harus berdasarkan karakteristik data aktual.

Studi Kasus: Pencarian ID Pengguna #

Bayangkan kita membangun sistem pencarian ID pengguna dengan:

Database berisi 10 juta ID berurutan (1, 2, 3, …, 10000000) — distribusi seragam.
Setiap pengguna rata-rata melakukan 5 pencarian per hari.
Target biasanya acak di seluruh rentang.

Analisis:

Data seragam → interpolation search cocok.
ID berurutan → exponential search tidak optimal (target jarang dekat awal).
Pencarian berulang → hemat sedikit komparasi berarti hemat jutaan operasi per hari.

Rekomendasi: interpolation search. Rata-rata 2-3 komparasi per pencarian vs 24 dengan binary search. Penghematan ~10× pada beban kerja harian.

Studi Kasus: Pencarian Timestamp Log #

Bayangkan kita mencari timestamp tertentu pada log yang diurutkan:

Log berisi 1 miliar entri dengan timestamp tersebar clustering (puncak di jam sibuk, sepi di malam hari) — tidak seragam.
Target biasanya dekat akhir (pencarian “log terbaru”).

Analisis:

Data tidak seragam → interpolation search bisa worst case O(n).
Target dekat akhir → exponential search dari awal akan lambat (perlu log₂(10^9) ≈ 30 lompatan).
Data terurut, target acak → binary search O(log n) konsisten.

Rekomendasi: binary search. Konsisten 30 komparasi, tidak ada skenario worst case buruk.

Rekomendasi Praktis #

Ringkasan Akhir Section 10 #

Linear search: tidak butuh prasyarat, O(n), pemenang untuk data kecil atau tidak terurut.
Binary search: butuh data terurut, O(log n), default untuk pencarian pada data terurut.
Lower/upper bound: variasi binary search untuk “elemen pertama ≥ v” / “elemen pertama > v”.
Binary search on answer: teknik untuk soal optimasi dengan predikat monoton, O(n log R).
Ternary search: untuk fungsi unimodal, O(log_{1.5} n).
Jump search: O(√n), cache-friendly untuk data besar.
Exponential search: O(log n), ideal untuk target dekat awal atau array tak terbatas.
Interpolation search: O(log log n) rata-rata untuk data seragam, O(n) worst case.

Pilihan algoritma bergantung pada: prasyarat data, ukuran, distribusi, posisi target, dan frekuensi pencarian. Tidak ada satu algoritma yang selalu menang — kenali karakteristik masalah, lalu pilih sesuai tabel dan decision tree di atas.