Binary Search

Binary search adalah algoritma pencarian yang memanfaatkan sifat data terurut untuk mengurangi ukuran masalah menjadi separuh pada setiap langkah. Alih-alih memeriksa elemen satu per satu, binary search membandingkan target dengan elemen tengah, lalu membuang setengah dari ruang pencarian. Hasilnya: kompleksitas turun dari O(n) menjadi O(log n). Pada data satu juta elemen, binary search hanya butuh paling banyak 20 perbandingan dibanding satu juta pada linear search. Pada Chapter ini kita akan mempelajari prinsip divide and conquer pada pencarian, dua bentuk implementasi (iteratif dan rekursif), serta fungsi STL seperti std::binary_search, std::lower_bound, dan std::upper_bound.

Prasyarat: Data Terurut #

Binary search hanya bekerja pada data terurut. Bila data tidak terurut, hasil binary search tidak terdefinisi — algoritma mungkin mengembalikan indeks acak atau “tidak ketemu” padahal target ada. Pastikan array terurut secara menaik (atau menurun, dengan penyesuaian logika) sebelum menerapkan binary search.

Aturan dan Mekanisme: Divide and Conquer #

Misalkan array a terurut menaik dengan indeks [0, n-1]. Kita mencari target:

1. Inisialisasi lo = 0, hi = n - 1.
2. Selama lo <= hi:
   • Hitung mid = lo + (hi - lo) / 2. Hindari (lo + hi) / 2 yang dapat overflow untuk angka besar.
   • Bila a[mid] == target: ketemu.
   • Bila a[mid] < target: target pasti di setengah kanan → lo = mid + 1.
   • Bila a[mid] > target: target pasti di setengah kiri → hi = mid - 1.
3. Bila loop selesai tanpa ketemu, target tidak ada.

Setiap iterasi membuang setengah elemen, sehingga jumlah iterasi maksimum adalah ceil(log2(n)).

Implementasi Iteratif #

Kode: Binary Search Iteratif #

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

std::optional<size_t> binary_search(const std::vector<int>& a, int target) {
    size_t lo = 0;
    size_t hi = a.size();  // exclusive upper bound initially, adjust below
    if (a.empty()) return std::nullopt;
    hi = 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 = {1, 3, 5, 7, 9, 11, 13};
    for (int t : {9, 1, 13, 8}) {
        auto res = binary_search(a, t);
        std::cout << "cari " << t << ": ";
        if (res) std::cout << "ketemu di indeks " << *res << '\n';
        else    std::cout << "tidak ketemu\n";
    }
    return 0;
}

Output yang Dihasilkan:

cari 9: ketemu di indeks 4
cari 1: ketemu di indeks 0
cari 13: ketemu di indeks 6
cari 8: tidak ketemu

1. Baris hi = a.size() - 1;: kita memakai rentang inklusif [lo, hi]. Bila array kosong, segera kembalikan nullopt untuk menghindari underflow size_t.
2. Baris size_t mid = lo + (hi - lo) / 2;: rumus alternatif dari (lo + hi) / 2 yang aman dari overflow. Untuk size_t, ekspresi lo + (hi - lo) / 2 tidak meluap selama hi >= lo.
3. Baris lo = mid + 1;: target lebih besar dari a[mid], jadi kita membuang mid dan seluruh elemen di kiri. Setengah kanan [mid+1, hi] tetap dieksplorasi.
4. Baris hi = mid - 1;: cermin dari kasus di atas — buang mid dan setengah kanan, eksplorasi [lo, mid-1].
5. Kondisi while (lo <= hi): loop berhenti bila lo > hi, artinya ruang pencarian kosong.

Implementasi Rekursif #

Binary search cocok diekspresikan secara rekursif karena secara natural mengikuti pola divide and conquer. Kedalaman rekursi hanya O(log n) sehingga stack overflow tidak menjadi masalah praktis bahkan untuk n sangat besar.

Kode: Binary Search Rekursif #

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

std::optional<size_t> bs_rec(
    const std::vector<int>& a, int target,
    size_t lo, size_t hi)
{
    if (lo > hi) return std::nullopt;       // base case: ruang kosong
    size_t mid = lo + (hi - lo) / 2;
    if (a[mid] == target) return mid;
    else if (a[mid] < target)
        return bs_rec(a, target, mid + 1, hi);
    else
        return bs_rec(a, target, lo, mid - 1);
}

int main() {
    std::vector<int> a = {1, 3, 5, 7, 9, 11, 13};
    auto res = bs_rec(a, 9, 0, a.size() - 1);
    if (res) std::cout << "ketemu di indeks " << *res << '\n';
    else    std::cout << "tidak ketemu\n";
    return 0;
}

Output yang Dihasilkan:

ketemu di indeks 4

1. Parameter lo, hi: dibawa sebagai argumen agar tidak perlu memodifikasi state global. Setiap pemanggilan rekursif membawa sub-rentang yang lebih kecil.
2. Baris if (lo > hi) return std::nullopt;: base case. Tidak ada elemen untuk diperiksa.
3. Baris return bs_rec(a, target, mid + 1, hi);: recursive case untuk setengah kanan. Kompleksitas ruang O(log n) untuk stack frame.
4. Kompleksitas: waktu O(log n), ruang O(log n) (rekursif) vs O(1) (iteratif).

Fungsi STL untuk Binary Search #

C++ menyediakan empat fungsi di <algorithm> yang memanfaatkan binary search:

Kode: Empat Fungsi STL #

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> a = {1, 3, 3, 3, 5, 7, 9};
    int v = 3;

    bool ada = std::binary_search(a.begin(), a.end(), v);
    std::cout << "binary_search(3): " << (ada ? "ya" : "tidak") << '\n';

    auto lb = std::lower_bound(a.begin(), a.end(), v);
    std::cout << "lower_bound(3): indeks "
              << std::distance(a.begin(), lb) << '\n';

    auto ub = std::upper_bound(a.begin(), a.end(), v);
    std::cout << "upper_bound(3): indeks "
              << std::distance(a.begin(), ub) << '\n';

    auto [lo, hi] = std::equal_range(a.begin(), a.end(), v);
    std::cout << "equal_range(3): ["
              << std::distance(a.begin(), lo) << ", "
              << std::distance(a.begin(), hi) << ")\n";
    return 0;
}

Output yang Dihasilkan:

binary_search(3): ya
lower_bound(3): indeks 1
upper_bound(3): indeks 4
equal_range(3): [1, 4)

1. Baris std::binary_search: hanya memberitahu ada/tidak, tanpa posisi. Implementasi di baliknya menggunakan lower_bound.
2. Baris std::lower_bound: posisi elemen pertama yang ≥ v. Untuk v = 3 pada array 1 3 3 3 5 7 9, elemen pertama ≥ 3 ada di indeks 1.
3. Baris std::upper_bound: posisi elemen pertama yang > v. Untuk v = 3, elemen pertama > 3 (yaitu 5) ada di indeks 4.
4. Baris std::equal_range: mengembalikan pasangan (lower_bound, upper_bound) sekaligus. Selisih hi - lo = jumlah elemen yang sama dengan v (di sini 3 elemen).

Binary Search dengan Komparator Kustom #

STL menerima komparator biner opsional. Misalnya, untuk array terurut menurun atau membandingkan field tertentu pada struct.

Kode: Binary Search pada vector<string> Sortir Kustom #

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

int main() {
    // Array terurut menurun
    std::vector<int> a = {9, 7, 5, 3, 1};
    auto cmp = std::greater<int>{};

    bool ada = std::binary_search(a.begin(), a.end(), 5, cmp);
    std::cout << "5 ada? " << (ada ? "ya" : "tidak") << '\n';

    auto lb = std::lower_bound(a.begin(), a.end(), 5, cmp);
    std::cout << "lower_bound(5): indeks "
              << std::distance(a.begin(), lb) << '\n';
    return 0;
}

Output yang Dihasilkan:

5 ada? ya
lower_bound(5): indeks 2

1. Baris auto cmp = std::greater<int>{};: komparator “lebih besar”. Karena array terurut menurun, kita harus memberi tahu STL bahwa elemen dianggap “lebih kecil” bila nilainya lebih besar.
2. Baris std::binary_search(a.begin(), a.end(), 5, cmp): STL memakai cmp untuk menentukan urutan. Hasilnya benar — 5 ada di indeks 2.
3. Kompleksitas: sama O(log n), hanya komparator yang diganti.

Ringkasan #

• Binary search bekerja pada data terurut dengan kompleksitas O(log n).
• Implementasi iteratif: ruang O(1). Implementasi rekursif: ruang O(log n).
• Selalu gunakan mid = lo + (hi - lo) / 2 untuk menghindari integer overflow.
• STL menyediakan binary_search, lower_bound, upper_bound, equal_range — pilih sesuai kebutuhan.
• Komparator kustom (std::greater, lambda) memungkinkan binary search pada data terurut menurun atau berbasis field struct.