Binary Search

Ketika data sudah terurut, kita tidak perlu memeriksa elemen satu per satu seperti std::find. Pencarian biner (binary search) membandingkan nilai yang dicari dengan elemen tengah rentang, lalu membuang separuh data yang pasti tidak memuatnya, dan mengulang langkah itu pada sisa separuhnya. Hasilnya kompleksitas O(log n): satu juta elemen cukup sekitar dua puluh perbandingan. C++ menyediakan empat algoritma keluarga ini di <algorithm> — std::binary_search, std::lower_bound, std::upper_bound, dan std::equal_range — dan semuanya membagi satu syarat mutlak: rentang yang diberikan harus sudah terurut sesuai comparator yang dipakai.

Syarat Mutlak: Data Terurut #

Algoritma ini bekerja dengan asumsi “di kiri lebih kecil, di kanan lebih besar”. Bila data belum terurut, asumsi itu runtuh dan hasilnya tidak bisa dipercaya: binary_search bisa melaporkan nilai tidak ada padahal ada, dan lower_bound bisa mengembalikan posisi sembarang. Standar tidak menyebut hasilnya error, tetapi tidak menjanjikan apa pun — pada praktiknya ini berarti bug yang sulit dilacak.

Satu detail yang mudah terlewat: keurutan yang dimaksud harus konsisten dengan comparator. binary_search tanpa comparator memakai operator<; bila kita menyortir dengan comparator khusus, comparator yang sama harus dikirim ke binary search.

Empat Algoritma, Empat Jawaban #

Algoritma	Pertanyaan yang dijawab	Hasil
`std::binary_search`	“Apakah nilainya ada?”	`bool`
`std::lower_bound`	“Elemen pertama yang >= nilai?”	iterator
`std::upper_bound`	“Elemen pertama yang > nilai?”	iterator
`std::equal_range`	“Rentang semua elemen yang == nilai?”	`pair` dua iterator

Program berikut memakai keempatnya pada data yang mengandung duplikat — situasi yang justru membedakan kegunaan masing-masing:

cpp

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

int main() {
    // Syarat mutlak: data WAJIB terurut menaik sebelum dipakai
    std::vector<int> data = {10, 20, 30, 40, 40, 40, 50};

    // binary_search: hanya menjawab ada / tidak ada (bool)
    std::cout << "30 ada? " << std::boolalpha
              << std::binary_search(data.begin(), data.end(), 30) << "\n";
    std::cout << "35 ada? " << std::boolalpha
              << std::binary_search(data.begin(), data.end(), 35) << "\n";

    // lower_bound: elemen pertama yang >= nilai
    auto lb = std::lower_bound(data.begin(), data.end(), 40);
    std::cout << "lower_bound(40): indeks " << (lb - data.begin()) << "\n";

    // upper_bound: elemen pertama yang > nilai
    auto ub = std::upper_bound(data.begin(), data.end(), 40);
    std::cout << "upper_bound(40): indeks " << (ub - data.begin()) << "\n";

    // equal_range: pasangan (lower_bound, upper_bound) dalam std::pair
    auto rentang = std::equal_range(data.begin(), data.end(), 40);
    std::cout << "40 muncul " << (rentang.second - rentang.first)
              << " kali, mulai indeks " << (rentang.first - data.begin()) << "\n";

    // lower_bound juga menyebutkan posisi sisip yang menjaga keurutan
    auto sisip = std::lower_bound(data.begin(), data.end(), 35);
    std::cout << "Sisip 35 di indeks " << (sisip - data.begin()) << "\n";
    return 0;
}

Output yang Dihasilkan:

text
30 ada? true
35 ada? false
lower_bound(40): indeks 3
upper_bound(40): indeks 6
40 muncul 3 kali, mulai indeks 3
Sisip 35 di indeks 3

Bedah baris demi baris:

Baris 7-10 (std::binary_search(..., 30) dan (..., 35)): pertanyaan keberadaan dijawab dengan bool saja — true untuk 30, false untuk 35. Cepat, tetapi tidak memberi tahu posisinya.
Baris 13-14 (std::lower_bound(..., 40)): tiga elemen pertama (10, 20, 30) lebih kecil dari 40, sehingga lower_bound berhenti di indeks 3 — elemen 40 pertama.
Baris 17-18 (std::upper_bound(..., 40)): upper_bound melewati semua elemen yang <= 40, sehingga berhenti di indeks 6 — elemen 50.
Baris 21-23 (std::equal_range(..., 40)): pasangan (lower_bound, upper_bound) menutup semua kemunculan 40. Selisih kedua iteratornya adalah jumlah kemunculan: tiga.
Baris 26-27: lower_bound(35) menunjuk indeks 3, posisi pertama yang nilainya >= 35. Menyisipkan 35 di situ membuat data tetap terurut — inilah asal nama “sisip”.

Pola lower_bound sebagai posisi sisip adalah idiom yang sering dipakai: menambahkan data ke vector terurut tanpa menyortir ulang seluruhnya.

Memilih yang Mana #

Gunakan binary_search bila cukup ya/tidak; lower_bound bila butuh posisi atau ingin menyisip terurut; upper_bound untuk batas atas kelompok nilai; dan equal_range untuk memotong atau menghitung semua kemunculan sekaligus. Untuk std::list yang bidirectional, lower_bound masih bisa dipakai namun keunggulan O(log n) hilang karena maju antar node tetap O(n) — keluarga ini memang dirancang untuk rentang random access seperti vector dan array.

Berikutnya kita beralih ke algoritma pembanding sederhana yang tidak menuntut data terurut: mencari elemen minimum dan maksimum.

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