Chapter sebelumnya berakhir pada angka yang menggoda: dengan satu asumsi tambahan — data terurut — pencarian 100.000 elemen cukup 16 perbandingan, bukan 77.777. Binary search adalah algoritma yang menghasilkan angka itu. Idenya sama seperti mencari kata di kamus: buka tengah, lalu buang separuh kandidat yang pasti salah, dan ulangi pada separuh yang tersisa. Binary search tree pada chapter BST adalah versi struktur data dari ide yang sama; di sini kita menjalankannya pada array terurut, dalam dua bentuk — iteratif dan rekursif — serta membahas satu jebakan klasik pada perhitungan titik tengah yang pernah menjadi bug nyata di library berumur puluhan tahun.

Versi Iteratif dan Rekursif #

Program berikut memuat kedua versi pada data yang sama, ditambah std::lower_bound sebagai pembanding dari STL:

cpp 
// Binary search iteratif dan rekursif, plus lower_bound dari STL.
#include <algorithm>
#include <iostream>
#include <vector>

// Versi iteratif: dua penunjuk lo dan hi menyempitkan rentang.
int cariIteratif(const std::vector<int>& data, int target, long long& perbandingan) {
    perbandingan = 0;
    int lo = 0;
    int hi = static_cast<int>(data.size()) - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;   // aman dari overflow
        ++perbandingan;
        if (data[mid] == target) return mid;
        if (data[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

// Versi rekursif: pembungkus menyetel penghitung, helper mengerjakan rekursi.
int cariBantu(const std::vector<int>& data, int target, int lo, int hi,
              long long& perbandingan) {
    if (lo > hi) return -1;             // basis: rentang habis
    int mid = lo + (hi - lo) / 2;
    ++perbandingan;
    if (data[mid] == target) return mid;
    if (data[mid] < target) {
        return cariBantu(data, target, mid + 1, hi, perbandingan);
    }
    return cariBantu(data, target, lo, mid - 1, perbandingan);
}

int cariRekursif(const std::vector<int>& data, int target, long long& perbandingan) {
    perbandingan = 0;
    return cariBantu(data, target, 0, static_cast<int>(data.size()) - 1,
                     perbandingan);
}

int main() {
    std::vector<int> terurut = {2, 4, 4, 4, 7, 9, 11};
    long long p = 0;

    std::cout << "cariIteratif(7) -> indeks "
              << cariIteratif(terurut, 7, p)
              << " (" << p << " perbandingan)\n";
    std::cout << "cariRekursif(7) -> indeks "
              << cariRekursif(terurut, 7, p)
              << " (" << p << " perbandingan)\n";
    std::cout << "cariIteratif(5) -> indeks "
              << cariIteratif(terurut, 5, p)
              << " (" << p << " perbandingan, target tidak ada)\n";

    // lower_bound: iterator ke elemen pertama yang >= target
    auto posisi4 = std::lower_bound(terurut.begin(), terurut.end(), 4);
    auto posisi5 = std::lower_bound(terurut.begin(), terurut.end(), 5);
    std::cout << "lower_bound(4) -> indeks "
              << (posisi4 - terurut.begin()) << " (duplikat: yang pertama)\n";
    std::cout << "lower_bound(5) -> indeks "
              << (posisi5 - terurut.begin()) << " (posisi sisip untuk 5)\n";

    // Skala besar: satu juta elemen terurut
    std::vector<int> besar;
    besar.reserve(1000000);
    for (int i = 1; i <= 1000000; ++i) besar.push_back(i);
    cariIteratif(besar, 999999, p);
    std::cout << "1 juta elemen, cari 999999  : " << p << " perbandingan\n";
    cariIteratif(besar, 1000001, p);
    std::cout << "1 juta elemen, cari 1000001 : " << p
              << " perbandingan (tidak ada)\n";
    return 0;
}

Output yang Dihasilkan:

text 
cariIteratif(7) -> indeks 4 (3 perbandingan)
cariRekursif(7) -> indeks 4 (3 perbandingan)
cariIteratif(5) -> indeks -1 (3 perbandingan, target tidak ada)
lower_bound(4) -> indeks 1 (duplikat: yang pertama)
lower_bound(5) -> indeks 4 (posisi sisip untuk 5)
1 juta elemen, cari 999999  : 19 perbandingan
1 juta elemen, cari 1000001 : 20 perbandingan (tidak ada)

Bedah baris penting:

  1. Baris 7-19 (cariIteratif): dua penunjuk lo dan hi membentuk rentang kandidat [lo, hi]; loop berjalan selama rentang tidak kosong.
  2. Baris 12 (mid): titik tengah yang aman dari overflow — dibedah khusus di bawah.
  3. Baris 15-16: perbandingan tidak sama artinya kita membuang separuh rentang: lo = mid + 1 atau hi = mid - 1. Penyesuaian +1/-1 wajib; tanpa itu rentang bisa berhenti menyusut dan loop tak pernah berakhir.
  4. Baris 22-32 (cariBantu): versi rekursif dari logika yang sama — basis lo > hi artinya rentang habis dan target tidak ada.
  5. Baris 34-38 (cariRekursif): pembungkus yang menyetel penghitung lalu memanggil helper; pola wrapper-plus-helper menjaga tanda tangan fungsi tetap rapi.
  6. Baris 55-60: std::lower_bound mengembalikan iterator ke elemen pertama yang >= target — untuk 4 yang duplikat, indeks 1 (yang pertama), dan untuk 5 yang tidak ada, indeks 4, tepat posisi penyisipan.

Jebakan Overflow pada Perhitungan Mid #

Cara menulis titik tengah yang paling intuitif adalah mid = (lo + hi) / 2. Tapi penjumlahan lo + hi bisa meluap sebelum pembagian sempat dilakukan: jika keduanya besar (misalnya sekitar 2 miliar pada tipe int), jumlahnya melewati batas INT_MAX, berubah menjadi negatif, dan mid menunjuk indeks yang tidak valid. Bug ini pernah terjadi di implementasi binarySearch JDK selama bertahun-tahun sebelum ditemukan pada tahun 2006.

Formula yang kita pakai, mid = lo + (hi - lo) / 2, menyelesaikannya: hi - lo selalu tidak negatif dan tidak melebihi panjang rentang, sehingga tidak ada penjumlahan dua nilai besar. Beda keduanya terlihat hanya pada input ekstrem, tapi kebiasaan menulis versi aman tidak menambah biaya apa pun. Semua compiler modern menghasilkan kode yang sama cepatnya, jadi tidak ada alasan untuk menulis versi rawan.

Syarat Terurut dan Skala Satu Juta Elemen #

Seluruh jaminan binary search bertumpu pada satu syarat: data terurut menaik. Jika syarat ini dilanggar, algoritma tetap berjalan tanpa error tetapi jawabannya tidak dapat dipercaya — ia membuang “separuh kandidat” berdasarkan asumsi yang sudah salah sejak awal. Itulah kenapa pemeriksaan seperti std::is_sorted pada data yang tidak Anda kendalikan bisa jadi penyelamat.

Skala terbesar di output menegaskan pertumbuhan logaritmiknya. Satu juta elemen hanya butuh 19 perbandingan untuk menemukan 999999 dan 20 untuk memastikan 1000001 tidak ada — kira-kira log₂(1.000.000) yang membulat ke atas. Menggandakan ukuran data hanya menambah satu perbandingan. Dua baris terakhir juga mengajarkan pola penghitungan: jumlah perbandingan untuk kasus “tidak ditemukan” selalu satu lebih banyak dari kasus ketemu terdalam, karena rentang harus menyusut sampai benar-benar kosong.

Binary search menuntut data yang sudah terurut, dan pertanyaan itu langsung memunculkan tugas baru: siapa yang mengurutkan, dengan cara apa, dan berapa biayanya? Chapter berikutnya menjawabnya dengan membangun tiga algoritma sorting secara manual dan mengukurnya dengan penghitung perbandingan yang sama seperti yang kita pakai di sini.

Rujukan resmi: std::binary_search dan std::lower_bound .