Binary Search on Answer

Banyak soal optimasi tidak meminta kita mencari elemen dalam array, melainkan menemukan nilai x* yang meminimalkan atau memaksimalkan suatu fungsi dengan batasan. Bayangkan soal split array largest sum: diberi array bilangan bulat positif dan integer k, partisi array menjadi k subarray kontigu sehingga jumlah maksimum subarray seminimal mungkin. Solusi brute force mencoba semua kemungkinan — eksponensial. Tetapi bila kita balik pertanyaannya — “apakah mungkin mempartisi sehingga setiap subarray berjumlah ≤ x?” — jawabannya menjadi monoton: bila bisa untuk x, pasti bisa untuk x' > x. Inilah monotonic predicate, dan di sinilah binary search bekerja. Pada Chapter ini kita akan mempelajari pola umum, tiga contoh klasik, dan analisis kompleksitas.

Pola Umum: Monotonic Predicate #

Binary search on answer bekerja bila:

1. Domain solusi terurut: x bisa diuji secara diskret (biasanya bilangan bulat), dan rentang [lo, hi] jelas.
2. Predikat monoton: P(x) true → P(y) true untuk semua y ≥ x (atau kebalikannya). Inilah kunci.
3. Subproblem O(n): tes P(x) dapat dijawab dalam waktu polinomial (umumnya O(n)).

Bila tiga syarat terpenuhi, kita binary search pada x bukan pada elemen array. Kompleksitas total: O(n log R), dengan R rentang domain solusi.

Contoh 1: Split Array Largest Sum #

Aturan #

Diberi array a bilangan bulat non-negatif dan integer k. Partisi array menjadi k subarray kontigu (setiap elemen masuk tepat satu subarray) sehingga jumlah maksimum antar subarray seminimal mungkin. Kembalikan nilai minimum tersebut.

Mekanisme #

Tentukan predikat P(x) = “apakah array dapat dipartisi menjadi ≤ k subarray sehingga setiap subarray berjumlah ≤ x?”. Predikat ini monoton menurun: bila x besar, lebih mudah dipenuhi; bila x kecil, lebih sulit. Kita cari x* terkecil sehingga P(x*) true.

Cara tes P(x): iterasi array, akumulasikan sum. Bila sum saat ini + elemen baru > x, mulai subarray baru. Hitung berapa subarray yang dipakai. Bila ≤ k, P(x) true.

Kode #

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

bool bisa_dipartisi(const std::vector<int>& a, int k, long long batas) {
    int subarray_count = 1;
    long long sum = 0;
    for (int x : a) {
        if (x > batas) return false;  // satu elemen saja sudah melampaui
        if (sum + x > batas) {
            ++subarray_count;
            sum = x;
        } else {
            sum += x;
        }
    }
    return subarray_count <= k;
}

long long split_array_largest_sum(const std::vector<int>& a, int k) {
    long long lo = *std::max_element(a.begin(), a.end());
    long long hi = std::accumulate(a.begin(), a.end(), 0LL);
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (bisa_dipartisi(a, k, mid)) hi = mid;
        else                            lo = mid + 1;
    }
    return lo;
}

int main() {
    std::vector<int> a = {7, 2, 5, 10, 8};
    int k = 2;
    std::cout << "minimum largest sum (k=2): "
              << split_array_largest_sum(a, k) << '\n';

    a = {1, 2, 3, 4, 5};
    k = 2;
    std::cout << "minimum largest sum (k=2): "
              << split_array_largest_sum(a, k) << '\n';
    return 0;
}

Output yang Dihasilkan:

minimum largest sum (k=2): 18
minimum largest sum (k=2): 9

1. Baris lo = *std::max_element(...): lower bound. Setiap partisi harus menampung setidaknya satu elemen, jadi batas minimal adalah elemen terbesar.
2. Baris hi = std::accumulate(...): upper bound. Bila k = 1, semua elemen dalam satu partisi → jumlah total.
3. Fungsi bisa_dipartisi: tes P(x) dalam O(n). Hitung jumlah subarray yang dibutuhkan bila setiap subarray ≤ batas.
4. Baris if (x > batas) return false;: kasus mustahil — satu elemen saja melampaui batas. Tidak ada partisi yang valid.
5. Baris if (sum + x > batas) { ++subarray_count; sum = x; }: elemen baru tidak muat di subarray saat ini, mulai subarray baru.
6. Baris if (bisa_dipartisi(a, k, mid)) hi = mid;: predikat true → coba nilai lebih kecil.
7. Hasil pertama: a = {7, 2, 5, 10, 8}, k = 2. Partisi optimal [7, 2, 5] dan [10, 8], jumlah maksimum max(14, 18) = 18.
8. Kompleksitas: O(n log R) dengan R = sum - max.

Contoh 2: Capacity to Ship Packages #

Aturan #

Diberi weights dan days. Kapal mengangkut paket berurutan (urutan array tidak boleh berubah). Kapasitas kapal minimum berapa sehingga semua paket dapat dikirim dalam days hari? Satu hari boleh mengangkut banyak paket selama total berat ≤ kapasitas.

Kode #

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

bool bisa_dikirim(const std::vector<int>& w, int days, long long cap) {
    int hari = 1;
    long long muat = 0;
    for (int x : w) {
        if (x > cap) return false;
        if (muat + x > cap) {
            ++hari;
            muat = x;
        } else {
            muat += x;
        }
    }
    return hari <= days;
}

long long ship_within_days(const std::vector<int>& w, int days) {
    long long lo = *std::max_element(w.begin(), w.end());
    long long hi = std::accumulate(w.begin(), w.end(), 0LL);
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (bisa_dikirim(w, days, mid)) hi = mid;
        else                            lo = mid + 1;
    }
    return lo;
}

int main() {
    std::vector<int> w = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int days = 5;
    std::cout << "kapasitas minimum: " << ship_within_days(w, days) << '\n';
    return 0;
}

Output yang Dihasilkan:

kapasitas minimum: 15

1. Struktur identik dengan split array: hanya konteks yang berbeda — partisi subarray = hari pengiriman. Predikat P(cap) = “bisa dikirim dalam ≤ days hari”.
2. Hasil 15: kapasitas 15 cukup. Pengiriman: [1,2,3,4,5]=15, [6,7]=13, [8]=8, [9]=9, [10]=10 → 5 hari. Kapasitas 14 tidak cukup karena paket terakhir 10 + paket 9 = 19 > 14, dan [8,9]=17 > 14.
3. Kompleksitas: O(n log(sum - max)).

Contoh 3: Koko dan Pisang #

Aturan #

Koko punya n tumpukan pisang, tumpukan ke-i berisi piles[i] pisang. Koko makan h pisang per jam — bila tumpukan kurang dari h, Koko makan semua lalu istirahat (tidak membawa sisa). Koko memiliki H jam. Berapa h minimum agar semua pisang habis?

Mekanisme #

Predikat P(h) = “dengan kecepatan h pisang per jam, semua tumpukan habis dalam ≤ H jam”. Monoton: h lebih besar → jam lebih sedikit. Cari h* terkecil.

Kode #

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

bool bisa_habis(const std::vector<int>& piles, int H, long long h) {
    long long jam = 0;
    for (int p : piles) {
        jam += (p + h - 1) / h;  // ceiling division
    }
    return jam <= H;
}

long long min_eating_speed(const std::vector<int>& piles, int H) {
    long long lo = 1;
    long long hi = *std::max_element(piles.begin(), piles.end());
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (bisa_habis(piles, H, mid)) hi = mid;
        else                            lo = mid + 1;
    }
    return lo;
}

int main() {
    std::vector<int> piles = {3, 6, 7, 11};
    int H = 8;
    std::cout << "kecepatan makan minimum: "
              << min_eating_speed(piles, H) << '\n';
    return 0;
}

Output yang Dihasilkan:

kecepatan makan minimum: 4

1. Baris lo = 1;: kecepatan minimum adalah 1 pisang/jam.
2. Baris hi = *std::max_element(...): kecepatan maksimum praktis — tumpukan terbesar selesai dalam 1 jam.
3. Baris jam += (p + h - 1) / h;: pembagian ceiling. Tumpukan p pisang dengan kecepatan h per jam membutuhkan ceil(p / h) jam.
4. Hasil h = 4: dengan kecepatan 4 → jam = ceil(3/4)+ceil(6/4)+ceil(7/4)+ceil(11/4) = 1+2+2+3 = 8. Pas dengan H = 8. Kecepatan 3 → 1+2+3+4 = 10 > 8.
5. Kompleksitas: O(n log(max_pile)).

Analisis Kompleksitas #

Verifikasi Numerik #

Mari kita verifikasi kompleksitas split_array_largest_sum dengan instrumentasi penghitung pemanggilan bisa_dipartisi:

Kode: Verifikasi Log Iterasi #

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

int g_tes_count = 0;

bool bisa_dipartisi(const std::vector<int>& a, int k, long long batas) {
    ++g_tes_count;
    int sub = 1;
    long long sum = 0;
    for (int x : a) {
        if (x > batas) return false;
        if (sum + x > batas) { ++sub; sum = x; }
        else sum += x;
    }
    return sub <= k;
}

long long split_array(const std::vector<int>& a, int k) {
    long long lo = *std::max_element(a.begin(), a.end());
    long long hi = std::accumulate(a.begin(), a.end(), 0LL);
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (bisa_dipartisi(a, k, mid)) hi = mid;
        else                            lo = mid + 1;
    }
    return lo;
}

int main() {
    std::vector<int> a = {7, 2, 5, 10, 8};
    int k = 2;
    g_tes_count = 0;
    long long hasil = split_array(a, k);
    std::cout << "jawaban: " << hasil << '\n';
    std::cout << "jumlah tes P(x): " << g_tes_count << '\n';
    std::cout << "rentang [lo, hi] awal: [10, 32]\n";
    std::cout << "log2(32 - 10 + 1) = " << log2(32 - 10 + 1) << '\n';
    return 0;
}

Output yang Dihasilkan:

jawaban: 18
jumlah tes P(x): 4
log2(32 - 10 + 1) = 4.52356

1. jumlah tes P(x): 4: binary search pada rentang [10, 32] (23 nilai) butuh paling banyak ceil(log2(23)) = 5 iterasi, tetapi konvergen dalam 4 karena jawaban 18 ditemukan sebelum iterasi terakhir.
2. Rumus: O(log R) dengan R = hi - lo + 1.
3. Total operasi: 4 iterasi × O(n) per iterasi = O(4n). Pada n = 5, total ≈ 20 operasi. Bandingkan dengan brute force yang mencoba semua 2^(n-1) = 16 cara partisi.

Ringkasan #

• Binary search on answer bekerja bila predikat P(x) monoton dan dapat diuji dalam waktu polinomial.
• Tiga soal klasik dengan pola sama: split array largest sum, capacity to ship packages, koko eating bananas.
• Tahapan: (1) identifikasi variabel x yang dicari; (2) rumuskan predikat P(x); (3) tentukan rentang [lo, hi]; (4) jalankan binary search first-true atau last-true.
• Kompleksitas total O(n log R), jauh lebih baik dari brute force eksponensial atau DP O(n² k).
• Trik kunci: tukar pertanyaan “apa jawaban optimum?” menjadi “apakah x mungkin sebagai jawaban?” — sisanya diserahkan oleh binary search.