Binary Search Variants

Banyak soal searching tidak meminta “apakah v ada?” melainkan pertanyaan yang lebih bernuansa: “elemen pertama ≥ v”, “elemen terakhir ≤ v”, atau “elemen terakhir yang memenuhi predikat monoton”. Semua pertanyaan ini dapat dijawab dengan binary search, tetapi loop dan kondisi harus disesuaikan. Pada Chapter ini kita akan mempelajari dua varian utama — lower bound dan upper bound — serta pola umum binary search dengan predikat monoton. Kita juga akan membandingkan dua konvensi rentang: [lo, hi] (inklusif) dan [lo, hi) (semi-inklusif) yang banyak dipakai di STL.

Lower Bound: Elemen Pertama `≥ v` #

Aturan #

Diberikan array terurut menaik a dan nilai v, cari indeks i terkecil sehingga a[i] ≥ v. Bila tidak ada elemen yang ≥ v (semua elemen < v), kembalikan n (yang berarti “setelah akhir array”).

Mekanisme #

Loop binary search yang dimodifikasi: kita tidak berhenti saat a[mid] == v, melainkan terus mencari ke kiri untuk memastikan tidak ada indeks lebih kecil yang juga ≥ v. Variabel ans menyimpan kandidat terbaik sejauh ini.

flowchart TD A["a = [1, 3, 3, 5, 7, 9], v = 3"] --> B["lo=0, hi=6, ans=6"] B --> C["mid=3, a[3]=5 ≥ 3 → ans=3, hi=2"] C --> D["mid=1, a[1]=3 ≥ 3 → ans=1, hi=0"] D --> E["mid=0, a[0]=1 < 3 → lo=1"] E --> F["lo > hi → return ans = 1"]

Kode: Lower Bound Manual #

cpp
#include <iostream>
#include <vector>

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

int main() {
    std::vector<int> a = {1, 3, 3, 5, 7, 9};
    for (int v : {3, 4, 10, 0}) {
        size_t i = lower_bound_manual(a, v);
        std::cout << "lower_bound(" << v << ") = " << i;
        if (i < a.size()) std::cout << " (a[i]=" << a[i] << ")";
        std::cout << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text
lower_bound(3) = 1 (a[i]=3)
lower_bound(4) = 3 (a[i]=5)
lower_bound(10) = 6
lower_bound(0) = 0 (a[i]=1)

Baris hi = a.size();: rentang [lo, hi) semi-inklusif. Nilai hi dapat sama dengan n untuk mewakili “setelah akhir”.
Baris if (a[mid] >= v) hi = mid;: mid adalah kandidat lower bound. Kita perbarui hi = mid (bukan mid - 1) agar mid tetap masuk rentang pencarian berikutnya.
Baris else lo = mid + 1;: a[mid] < v, jadi mid dan seluruh elemen di kirinya pasti < v. Buang hingga mid + 1.
Kondisi while (lo < hi): berhenti saat lo == hi. Pada titik ini, lo adalah lower bound yang dicari.
Kasus v = 10: tidak ada elemen ≥ 10, kembalikan n = 6.
Kompleksitas: O(log n).

Upper Bound: Elemen Pertama `> v` #

Aturan #

Cari indeks i terkecil sehingga a[i] > v. Beda dengan lower bound: tanda > bukan ≥. Untuk v yang ada duplikatnya, upper bound berada setelah semua duplikat.

Kode: Upper Bound Manual #

cpp
#include <iostream>
#include <vector>

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

int main() {
    std::vector<int> a = {1, 3, 3, 5, 7, 9};
    for (int v : {3, 7, 9, 10}) {
        size_t i = upper_bound_manual(a, v);
        std::cout << "upper_bound(" << v << ") = " << i;
        if (i < a.size()) std::cout << " (a[i]=" << a[i] << ")";
        std::cout << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text
upper_bound(3) = 3 (a[i]=5)
upper_bound(7) = 5 (a[i]=9)
upper_bound(9) = 6
upper_bound(10) = 6

Baris if (a[mid] > v) hi = mid;: perbedaan dengan lower bound adalah tanda >. Elemen yang sama dengan v tidak memenuhi, jadi kita geser lo ke kanan melewati mereka.
Hasil upper_bound(3) = 3: elemen pertama > 3 adalah 5 di indeks 3. Tiga elemen 1, 3, 3 (indeks 0, 1, 2) ≤ 3.
Hasil upper_bound(10) = 6: tidak ada elemen > 10, kembalikan n.

Aplikasi: Hitung Frekuensi Elemen #

Kombinasi lower bound dan upper bound memberi jumlah elemen yang sama dengan v dalam array terurut — semuanya dalam O(log n).

Kode: Hitung Frekuensi O(log n) #

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

size_t count_freq(const std::vector<int>& a, int v) {
    auto lo = std::lower_bound(a.begin(), a.end(), v);
    auto hi = std::upper_bound(a.begin(), a.end(), v);
    return std::distance(lo, hi);
}

int main() {
    std::vector<int> a = {1, 2, 2, 2, 3, 3, 4, 5, 5, 5};
    for (int v : {2, 3, 5, 6}) {
        std::cout << "frekuensi " << v << ": " << count_freq(a, v) << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text
frekuensi 2: 3
frekuensi 3: 2
frekuensi 5: 3
frekuensi 6: 0

Baris auto lo = std::lower_bound(...): indeks elemen pertama ≥ v.
Baris auto hi = std::upper_bound(...): indeks elemen pertama > v.
Baris return std::distance(lo, hi);: selisih iterator = jumlah elemen == v. Semua elemen di rentang [lo, hi) bernilai persis v.
Kompleksitas: dua binary search O(log n) + satu pengurangan O(1) = O(log n) total.

Binary Search dengan Predikat Monoton #

Pola umum yang melampaui lower/upper bound: binary search dengan predikat boolean P(x) yang monoton — bila P(x) true, maka P(y) untuk semua y ≥ x juga true (atau kebalikannya). Kita cari titik transisi x* terkecil sehingga P(x*) true.

Aturan: First True #

Diberikan rentang [lo, hi] dan predikat monoton P(x), cari x* terkecil sehingga P(x*) true. Asumsi: P(hi) true (invariant).

Kode: First True dengan Lambda #

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

// Cari x terkecil di [lo, hi] sehingga P(x) true.
long long first_true(long long lo, long long hi,
                     bool(*P)(long long)) {
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (P(mid)) hi = mid;
        else         lo = mid + 1;
    }
    return lo;
}

bool akar_kuadrat_lebih(long long x) {
    // true bila x*x >= 1000  (monoton menaik)
    return x * x >= 1000;
}

int main() {
    long long x = first_true(1, 100, akar_kuadrat_lebih);
    std::cout << "akar terkecil x sehingga x^2 >= 1000: " << x << '\n';
    std::cout << "verifikasi: " << x << "^2 = " << x*x << '\n';
    return 0;
}

Output yang Dihasilkan:

text

akar terkecil x sehingga x^2 >= 1000: 32
verifikasi: 32^2 = 1024

Baris bool(*P)(long long): parameter berupa function pointer. Sama polanya berlaku untuk std::function atau lambda.
Baris if (P(mid)) hi = mid;: predikat true → mid adalah kandidat; cari lebih kiri.
Baris else lo = mid + 1;: predikat false → buang mid dan kiri.
Hasil x = 32: 31^2 = 961 < 1000, 32^2 = 1024 ≥ 1000. Sesuai.

Konvensi Rentang: `[lo, hi]` vs `[lo, hi)` #

Dua konvensi umum untuk rentang binary search:

Konvensi	Loop	Update `hi`	Update `lo`	STL?
`[lo, hi]` inklusif	`while (lo <= hi)`	`hi = mid - 1`	`lo = mid + 1`	Tidak
`[lo, hi)` semi-inklusif	`while (lo < hi)`	`hi = mid`	`lo = mid + 1`	Ya

STL memakai konvensi [lo, hi) (semi-inklusif). Konvensi ini nyaman karena:

hi = n valid sebagai “akhir array” tanpa off-by-one.
Update hi = mid (bukan mid - 1) menyimpan mid dalam rentang untuk iterasi berikutnya.
Loop berhenti saat lo == hi, dan saat itu lo adalah jawaban.

Varian: Last True (Elemen Terakhir yang Memenuhi) #

Cermin dari first true: cari x* terbesar sehingga P(x*) true. Asumsi P(lo) true.

Kode: Last True #

cpp
#include <iostream>

long long last_true(long long lo, long long hi,
                    bool(*P)(long long)) {
    while (lo < hi) {
        long long mid = lo + (hi - lo + 1) / 2;  // ceiling
        if (P(mid)) lo = mid;
        else         hi = mid - 1;
    }
    return lo;
}

bool maksimal(long long x) {
    return x * x <= 1000;  // true selama x^2 <= 1000
}

int main() {
    long long x = last_true(1, 100, maksimal);
    std::cout << "x terbesar dengan x^2 <= 1000: " << x << '\n';
    std::cout << "verifikasi: " << x << "^2 = " << x*x << '\n';
    return 0;
}

Output yang Dihasilkan:

text

x terbesar dengan x^2 <= 1000: 31
verifikasi: 31^2 = 961

Baris mid = lo + (hi - lo + 1) / 2;: pembagian ceiling (pembulatan ke atas). Penting agar mid > lo saat lo + 1 == hi, untuk mencegah infinite loop.
Baris if (P(mid)) lo = mid;: predikat true → mid adalah kandidat; cari lebih kanan.
Baris else hi = mid - 1;: predikat false → buang mid dan kanan.
Hasil x = 31: 31^2 = 961 ≤ 1000, 32^2 = 1024 > 1000. Sesuai.

Ringkasan #

Lower bound: indeks elemen pertama ≥ v. Update hi = mid saat a[mid] ≥ v.
Upper bound: indeks elemen pertama > v. Update hi = mid saat a[mid] > v.
Frekuensi elemen pada array terurut = upper_bound - lower_bound, semuanya O(log n).
Binary search dengan predikat monoton: generalisasi yang mencari titik transisi true/false.
First true (update hi = mid) dan last true (update lo = mid, mid = ceiling) adalah dua varian paling umum.
Konvensi [lo, hi) semi-inklusif lebih aman dan konsisten dengan STL.

Lower Bound: Elemen Pertama ≥ v #

Aturan #

Mekanisme #

Kode: Lower Bound Manual #

Upper Bound: Elemen Pertama > v #

Aturan #

Kode: Upper Bound Manual #

Aplikasi: Hitung Frekuensi Elemen #

Kode: Hitung Frekuensi O(log n) #

Binary Search dengan Predikat Monoton #

Aturan: First True #

Kode: First True dengan Lambda #

Konvensi Rentang: [lo, hi] vs [lo, hi) #

Varian: Last True (Elemen Terakhir yang Memenuhi) #

Kode: Last True #

Ringkasan #

Lower Bound: Elemen Pertama `≥ v` #

Upper Bound: Elemen Pertama `> v` #

Konvensi Rentang: `[lo, hi]` vs `[lo, hi)` #