Pencarian biner atas jawaban

Sebagian soal tidak meminta elemen di dalam array, melainkan sebuah angka yang memenuhi syarat, misalnya kecepatan minimum agar pekerjaan selesai tepat waktu atau kapasitas minimum agar beban terbagi habis. Bila syaratnya monoton, jawabannya dapat dicari dengan pencarian biner pada ruang jawaban, bukan pada array. Topik ini membedah keluarga soal optimasi min-maks tersebut lewat satu kasus yang diimplementasikan utuh dalam Python dan Java, lengkap dengan jejak setiap uji predikatnya.

Predikat monoton pada ruang jawaban#

Yang dicari dalam keluarga soal ini adalah nilai terkecil yang memenuhi sebuah syarat, atau nilai terbesarnya, dan syarat itu dirumuskan sebagai fungsi yang jawabannya ya atau tidak, disebut predikat (predicate). Predikat disebut monoton ketika satu jawaban ya menjamin semua nilai yang lebih besar juga ya, atau kebalikannya. Akibatnya rentang jawaban terbelah bersih menjadi daerah tidak dan daerah ya tanpa campuran, dan batas antar keduanya itulah yang dikejar.

Begitu monotonisitasnya pasti, templat rentang tertutup dari topik pencarian biner dipakai kembali apa adanya, hanya saja yang dipecah adalah ruang jawaban dan yang diuji adalah predikat. Pada setiap langkah, nilai tengah ruang diuji dengan predikat. Kandidat yang memadai menyempitkan ruang dari atas, karena yang dicari adalah nilai minimum yang masih memadai. Kandidat yang gagal menyempitkan ruang dari bawah. Biayanya $O(\log k)$ kali biaya satu kali uji predikat untuk ruang berukuran $k$, jauh lebih murah daripada menguji setiap kandidat satu per satu.

Soal kecepatan minimum#

Sebuah antrian dokumen berisi lima berkas dengan jumlah halaman 30, 11, 23, 4, dan 20. Mesin pengganda disetel pada kecepatan bulat $k$ halaman per jam dan mengerjakan dokumen satu per satu, sehingga satu dokumen berisi $h$ halaman memakan waktu $\lceil h / k \rceil$ jam. Pertanyaannya, berapa kecepatan minimum agar seluruh dokumen selesai dalam paling lama 8 jam? Total waktunya mengikuti rumus berikut.

Predikatnya adalah jam(k) <= batas, yang hasilnya selalu turun seiring $k$ naik, jadi monoton. Ruang jawabannya dibatasi 1 sampai halaman terbanyak, karena kecepatan setara dokumen terbesar sudah menyelesaikan setiap dokumen dalam paling lama satu jam, sedangkan jawaban di bawah 1 tidak bermakna. Rentang itulah yang dicari pencarian biner, dan setiap uji predikatnya berarti menghitung total jam untuk satu kandidat kecepatan.

"""Pencarian biner atas ruang jawaban: kecepatan minimum mesin pengganda dokumen."""


def jam_kerja(dokumen, kecepatan):
    """Total jam untuk menyelesaikan semua dokumen pada suatu kecepatan."""
    jam = 0
    for halaman in dokumen:
        jam += (halaman + kecepatan - 1) // kecepatan   # pembulatan ke atas
    return jam


def kecepatan_minimum(dokumen, batas):
    """Cari kecepatan bulat minimum agar selesai dalam batas jam; kembalikan (jawaban, jejak)."""
    kiri, kanan = 1, max(dokumen)
    jejak = []
    while kiri <= kanan:
        tengah = kiri + (kanan - kiri) // 2
        jam = jam_kerja(dokumen, tengah)
        jejak.append((tengah, jam, jam <= batas))
        if jam <= batas:
            kanan = tengah - 1    # kecepatan ini memadai, jawaban bisa lebih kecil
        else:
            kiri = tengah + 1     # kecepatan ini belum cukup
    return kiri, jejak


if __name__ == "__main__":
    dokumen = [30, 11, 23, 4, 20]
    batas = 8
    jawaban, jejak = kecepatan_minimum(dokumen, batas)
    print("dokumen :", dokumen)
    print("batas   :", batas, "jam")
    for tengah, jam, sah in jejak:
        keterangan = "ya" if sah else "tidak"
        print(f"  uji kecepatan {tengah:2} -> {jam:2} jam, memadai {keterangan}")
    print("jawaban :", jawaban, "halaman per jam")

    # pembanding: penyisiran linear pada ruang jawaban yang sama
    kandidat = 1
    while jam_kerja(dokumen, kandidat) > batas:
        kandidat += 1
    print("linear  :", kandidat, f"halaman per jam setelah {kandidat} uji")

dokumen : [30, 11, 23, 4, 20]
batas   : 8 jam
  uji kecepatan 15 ->  8 jam, memadai ya
  uji kecepatan  7 -> 15 jam, memadai tidak
  uji kecepatan 11 -> 10 jam, memadai tidak
  uji kecepatan 13 ->  9 jam, memadai tidak
  uji kecepatan 14 ->  9 jam, memadai tidak
jawaban : 15 halaman per jam
linear  : 15 halaman per jam setelah 15 uji

Keluaran mencatat lima uji, yaitu kecepatan 15 yang langsung memadai, lalu 7, 11, 13, dan 14 yang semuanya belum cukup. Setelah rentangnya menyempit hingga kiri melewati kanan, jawaban 15 dikembalikan, dan baris terakhir membandingkannya dengan penyisiran linear yang menguji 1, 2, 3, hingga 15, lima belas uji untuk jawaban yang sama. Selisih tiga kali lipat pada ruang sekecil ini membengkak menjadi ratusan kali lipat ketika ruang jawabannya membesar.

Membaca jejak uji dan versi Java#

Jejak uji memperlihatkan cara pencarian biner bergerak pada ruang jawaban. Uji pertama jatuh pada tengah rentang 1 sampai 30, yaitu kecepatan 15, dan karena hasilnya memadai, seluruh ruang di atasnya langsung dinyatakan tak perlu diuji. Empat uji berikutnya menyapu sisi bawah ruang, dan setiap jawaban yang tidak memadai menggeser batas kiri naik. Pola pembuangan separuh ruang inilah yang membuat jumlah ujinya tetap logaritmik walaupun yang diuji bukan elemen array.

Versi Java memakai struktur yang sama, dengan predikat sebagai metode jamKerja dan jawaban yang dikembalikan bersama jumlah ujinya melalui array dua elemen. Keluarannya menyatakan jawaban 15 halaman per jam dari lima uji, identik dengan versi Python, termasuk hasil penyisiran linear pembandingnya.

import java.util.Arrays;

public class KecepatanMinimum {

    // total jam untuk menyelesaikan semua dokumen pada suatu kecepatan
    static int jamKerja(int[] dokumen, int kecepatan) {
        int jam = 0;
        for (int halaman : dokumen) {
            jam += (halaman + kecepatan - 1) / kecepatan;   // pembulatan ke atas
        }
        return jam;
    }

    static int maksimum(int[] data) {
        int hasil = data[0];
        for (int nilai : data) {
            if (nilai > hasil) {
                hasil = nilai;
            }
        }
        return hasil;
    }

    // pencarian biner pada ruang jawaban 1 sampai dokumen terbesar
    // mengembalikan {jawaban, jumlah uji}
    static int[] kecepatanMinimum(int[] dokumen, int batas) {
        int kiri = 1, kanan = maksimum(dokumen), uji = 0;
        while (kiri <= kanan) {
            int tengah = kiri + (kanan - kiri) / 2;
            uji++;
            if (jamKerja(dokumen, tengah) <= batas) {
                kanan = tengah - 1;   // kecepatan ini memadai, jawaban bisa lebih kecil
            } else {
                kiri = tengah + 1;    // kecepatan ini belum cukup
            }
        }
        return new int[] {kiri, uji};
    }

    public static void main(String[] args) {
        int[] dokumen = {30, 11, 23, 4, 20};
        int batas = 8;
        int[] hasil = kecepatanMinimum(dokumen, batas);
        System.out.println("dokumen : " + Arrays.toString(dokumen));
        System.out.println("batas   : " + batas + " jam");
        System.out.println("jawaban : " + hasil[0] + " halaman per jam");
        System.out.println("uji     : " + hasil[1] + " kali");

        // pembanding: penyisiran linear pada ruang jawaban yang sama
        int kandidat = 1;
        while (jamKerja(dokumen, kandidat) > batas) {
            kandidat++;
        }
        System.out.println("linear  : " + kandidat + " halaman per jam setelah " + kandidat + " uji");
    }
}

dokumen : [30, 11, 23, 4, 20]
batas   : 8 jam
jawaban : 15 halaman per jam
uji     : 5 kali
linear  : 15 halaman per jam setelah 15 uji

# menjalankan berkas Java tunggal tanpa tahap kompilasi terpisah
java KecepatanMinimum.java

dokumen : [30, 11, 23, 4, 20]
batas   : 8 jam
jawaban : 15 halaman per jam
uji     : 5 kali
linear  : 15 halaman per jam setelah 15 uji

Keluarga soal yang dicakup pola ini jauh lebih besar daripada satu contohnya. Kapasitas minimum untuk membagi beban berurutan ke sejumlah pekerja, hari minimum menuntaskan tugas dengan kecepatan tertentu, dan jumlah perangkat minimum untuk menangani antrian permintaan semuanya mengikuti cetakan yang sama. Polanya selalu tiga langkah, rumuskan predikat, pastikan monoton, tetapkan rentang jawaban yang pasti memuat hasilnya, lalu biarkan pencarian biner menyempitkannya.

Kesalahan umum#

1. Mengasumsikan monoton tanpa mengujinya. Predikat yang naik turun membuat pencarian biner melaporkan jawaban yang salah tanpa satu pun pesan error. Periksa monotonisitasnya secara logis, atau dengan tabel uji kecil pada beberapa kandidat, sebelum menerapkan pencarian biner.
2. Rentang jawaban yang terlalu sempit. Batas atas harus berupa nilai yang pasti memadai, misalnya halaman terbanyak pada soal ini. Bila batas atasnya gagal juga, jawaban sejati berada di luar rentang dan pencarian mengembalikan satu nilai di atasnya yang keliru.
3. Mencampur dua pola pencarian jawaban. Ada dua pola yang sama-sama sah, yaitu pola rentang tertutup yang berhenti ketika kiri melewati kanan, dan pola yang mencatat jawaban memadai lalu terus menyempit. Campuran keduanya justru menimbulkan off-by-one. Pilih satu pola dan tetap konsisten, sama seperti pada templat array.

Ringkasan#

• Soal optimasi min-maks yang syaratnya monoton dapat dijawab dengan pencarian biner pada ruang jawaban, bukan pada array.
• Predikat diuji pada nilai tengah ruang, kandidat yang memadai menyempitkan ruang dari atas, kandidat yang gagal menyempitkannya dari bawah.
• Pada kasus kecepatan minimum, lima uji cukup untuk ruang jawaban 1 sampai 30, sementara penyisiran linear butuh lima belas uji untuk jawaban yang sama.
• Tiga syarat keberhasilannya, predikat yang benar-benar monoton, rentang jawaban yang pasti memuat hasil, dan pembaruan batas yang konsisten dengan satu pola.

Referensi#

• Binary search algorithm — Wikipedia — prinsip pembelahan ruang pencarian yang menjadi dasar pencarian biner atas jawaban.