KAL
Menu

Pencarian biner

Templat klasik pencarian biner dan kehati-hatian pada batas perulangannya.

Daftar isi

Pencarian biner menemukan sebuah nilai pada array terurut dengan membuang separuh kandidat pada setiap langkah, sehingga pencarian pada satu juta elemen selesai dalam sekitar dua puluh langkah. Topik ini menetapkan satu templat yang dipakai sepanjang jalur, yaitu rentang tertutup dari kiri sampai kanan. Jumlah langkahnya diukur untuk memperlihatkan pertumbuhan logaritmik. Dua perangkap yang paling sering menimbulkan jawaban salah atau perulangan tak berhingga kemudian dibedah, yaitu kesalahan off-by-one dan pembaruan batas yang tidak menyusutkan rentang.

Templat rentang tertutup#

Templat ini menjaga satu invarian, yaitu target, bila memang ada, selalu berada di dalam rentang tertutup [kiri, kanan] yang masih tersisa. Setiap langkah memeriksa elemen tengah, lalu membuang separuh rentang beserta tengahnya, karena tengah sudah teruji dan tidak boleh masuk rentang berikutnya. Perulangan berhenti ketika kiri melewati kanan, tanda rentangnya sudah kosong dan target tidak ada di array.

Rumus tengah ditulis kiri + (kanan - kiri) // 2, bukan (kiri + kanan) // 2, demi alasan yang baru terasa pada Java dan dibedah di bagian versi Java. Pembaruan batas juga tidak boleh setengah hati, kiri harus menjadi tengah + 1 dan kanan harus menjadi tengah - 1. Melonggarkan salah satu aturan itu membuka celah off-by-one, dan hal itu diperlihatkan secara nyata di bagian perangkap.

python pencarian-biner.py 
"""Templat pencarian biner pada rentang tertutup beserta penghitung langkah."""


def cari_biner(data, target):
    """Cari target pada array terurut; kembalikan (indeks, langkah)."""
    kiri, kanan = 0, len(data) - 1
    langkah = 0
    while kiri <= kanan:
        langkah += 1
        tengah = kiri + (kanan - kiri) // 2
        if data[tengah] == target:
            return tengah, langkah
        if data[tengah] < target:
            kiri = tengah + 1     # separuh kiri beserta tengahnya dibuang
        else:
            kanan = tengah - 1    # separuh kanan beserta tengahnya dibuang
    return -1, langkah


if __name__ == "__main__":
    data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
    for target in (23, 70):
        indeks, langkah = cari_biner(data, target)
        print(f"target {target} -> indeks {indeks}, langkah {langkah}")

    # jumlah langkah kasus terburuk tumbuh seperti log2 dari n
    for n in (10, 100, 1000, 1_000_000):
        _, langkah = cari_biner(list(range(n)), n)   # target tak pernah ada
        print(f"n {n} -> langkah terburuk {langkah}")
text Keluaran 
target 23 -> indeks 5, langkah 3
target 70 -> indeks -1, langkah 3
n 10 -> langkah terburuk 4
n 100 -> langkah terburuk 7
n 1000 -> langkah terburuk 10
n 1000000 -> langkah terburuk 20

Pencarian 23 pada array sepuluh elemen selesai dalam tiga langkah, yaitu rentang 0 sampai 9 memeriksa 16, rentang 5 sampai 9 memeriksa 56, lalu rentang 5 sampai 6 menemukan 23 pada indeks 5. Target 70 yang tidak ada juga selesai dalam tiga langkah, rentangnya terus menyusut hingga kosong dan fungsi mengembalikan -1. Dua hasil yang berbeda dengan jumlah langkah yang sama itulah wujud pertumbuhan logaritmik.

Jumlah langkah tumbuh logaritmik#

Kasus terburuk pada rentang tertutup menuntut ⌊log⁡2n⌋+1\lfloor \log_2 n \rfloor + 1 langkah, karena setiap langkah menyusutkan rentang menjadi paling banyak separuhnya. Keluaran program memperlihatkan pola itu secara berurutan, nn sebesar 10 butuh 4 langkah, 100 butuh 7, 1000 butuh 10, dan sejuta butuh 20. Setiap penambahan satu digit desimal pada nn hanya menambah satu atau dua langkah, selisih yang tak terbayangkan dibandingkan dengan pencarian linear yang menyusuri seluruh isi.

Diagram berikut mengikuti ketiga langkah pencarian 23, dari rentang penuh 0 sampai 9, tersisa 5 sampai 9, hingga 5 sampai 6 yang berujung pada penemuan. Warna kuning menandai elemen tengah yang diperiksa pada langkah itu, sedangkan sel pudar adalah kandidat yang sudah dibuang.

pembelahan rentang saat mencari 23rentang tertutup [kiri, kanan]langkah 1, rentang 0-925812162338567291langkah 2, rentang 5-925812162338567291langkah 3, rentang 5-625812162338
Pembelahan rentang pencarian biner saat mencari 23 pada array sepuluh elemen, tiga langkah hingga ditemukan

Syarat semua itu adalah array yang sudah terurut, karena pembuangan separuh kandidat hanya sah bila urutannya dapat diandalkan. Bila pencarian dilakukan berkali-kali pada data yang sama, biaya pengurutan sekali terbayar oleh setiap pencarian berikutnya yang hanya O(log⁡n)O(\log n). Pustaka bawaan pun menyediakan bentuk jadinya, yaitu modul bisect pada Python dan Arrays.binarySearch pada Java, dan keduanya menuntut masukan terurut dengan alasan yang sama.

Perangkap off-by-one dan perulangan tak berhingga#

Dua invarian yang populer adalah rentang tertutup [kiri, kanan] dan rentang setengah-terbuka [kiri, kanan). Keduanya sah, tetapi keduanya menuntut kondisi perulangan dan pembaruan batas yang berbeda. Kesalahan yang paling sering muncul adalah mencampur keduanya, misalnya memakai batas kanan = len(data) - 1 sambil menggantikan kondisi perulangan dengan kiri < kanan, sebagaimana diuji potongan berikut.

python Contoh: kondisi kiri < kanan pada rentang tertutup melewatkan elemen terakhir 
# batas kanan = len(data) - 1 dipadukan dengan kondisi kiri < kanan
data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]

def cari_salah(data, target):
    kiri, kanan = 0, len(data) - 1
    while kiri < kanan:
        tengah = (kiri + kanan) // 2
        if data[tengah] == target:
            return tengah
        if data[tengah] < target:
            kiri = tengah + 1
        else:
            kanan = tengah - 1
    return -1

print("target 91 ->", cari_salah(data, 91))
print("target 23 ->", cari_salah(data, 23))
text Keluaran 
target 91 -> -1
target 23 -> 5

Keluarannya memperlihatkan akibat yang nyata, target 91 yang berada di indeks terakhir dilaporkan tidak ditemukan, karena perulangan berhenti ketika kiri sama dengan kanan, tepat sebelum elemen terakhir sempat diperiksa. Target 23 yang kebetulan jatuh di tengah tetap ditemukan, sehingga bug semacam ini lolos dari uji kasual. Perbaikannya ada dua pilihan yang konsisten, mengembalikan kondisi kiri <= kanan untuk rentang tertutup, atau menggeser batas atas menjadi len(data) dengan pembaruan kanan = tengah untuk rentang setengah-terbuka.

Perangkap kedua terjadi ketika rentang tidak menyusut. Dengan tengah yang selalu terbulatkan ke bawah, pembaruan kiri = tengah ketika target lebih besar dari semua elemen membuat tengah berulang kali jatuh pada sel yang sama, dan perulangannya tidak pernah berhenti.

python Contoh: pembaruan kiri = tengah memicu perulangan tak berhingga 
# tidak-dijalankan
# Dengan tengah = kiri + (kanan - kiri) // 2 yang selalu terbulatkan ke bawah,
# pembaruan kiri = tengah pada target yang lebih besar dari semua elemen
# membuat tengah tidak pernah bergeser, sehingga perulangannya tidak berhenti.
def cari_macet(data, target):
    kiri, kanan = 0, len(data) - 1
    while kiri <= kanan:
        tengah = kiri + (kanan - kiri) // 2
        if data[tengah] < target:
            kiri = tengah          # seharusnya tengah + 1
        else:
            kanan = tengah - 1
    return -1

Versi Java dan luapan bilangan bulat#

Tipe int Java berukuran 32 bit dengan nilai maksimum 2147483647, sehingga penjumlahan kiri + kanan dapat meluap ketika kedua indeksnya besar, dan hasil yang meluap menjadi negatif tanpa pesan error apa pun. Rumus kiri + (kanan - kiri) / 2 menghindari luapan itu karena penjumlahannya tidak pernah melebihi kanan. Demo berikut menempatkan kedua indeks dekat batas tipe untuk memperlihatkan selisih kedua rumus secara nyata.

java PencarianBinerDemo.java 
public class PencarianBinerDemo {

    static int langkah;

    // pencarian biner pada rentang tertutup; mengembalikan indeks atau -1
    static int cariBiner(int[] data, int target) {
        int kiri = 0, kanan = data.length - 1;
        langkah = 0;
        while (kiri <= kanan) {
            langkah++;
            int tengah = kiri + (kanan - kiri) / 2;
            if (data[tengah] == target) {
                return tengah;
            }
            if (data[tengah] < target) {
                kiri = tengah + 1;    // separuh kiri beserta tengahnya dibuang
            } else {
                kanan = tengah - 1;   // separuh kanan beserta tengahnya dibuang
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] data = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
        int[] target = {23, 70};
        for (int t : target) {
            int indeks = cariBiner(data, t);
            System.out.println("target " + t + " -> indeks " + indeks + ", langkah " + langkah);
        }
        int[] ukuran = {10, 100, 1000, 1000000};
        for (int n : ukuran) {
            int[] urut = new int[n];
            for (int i = 0; i < n; i++) {
                urut[i] = i;
            }
            cariBiner(urut, n);   // target tidak pernah ada, kasus terburuk
            System.out.println("n " + n + " -> langkah terburuk " + langkah);
        }
        // alasan penulisan tengah = kiri + (kanan - kiri) / 2 pada Java
        int kiri = 1_500_000_000, kanan = 1_700_000_000;
        int tengahNaif = (kiri + kanan) / 2;
        int tengahAman = kiri + (kanan - kiri) / 2;
        System.out.println("tengah naif: " + tengahNaif + " (negatif akibat luapan)");
        System.out.println("tengah aman: " + tengahAman);
    }
}
text Keluaran 
target 23 -> indeks 5, langkah 3
target 70 -> indeks -1, langkah 3
n 10 -> langkah terburuk 4
n 100 -> langkah terburuk 7
n 1000 -> langkah terburuk 10
n 1000000 -> langkah terburuk 20
tengah naif: -547483648 (negatif akibat luapan)
tengah aman: 1600000000
bash 
# menjalankan berkas Java tunggal tanpa tahap kompilasi terpisah
java PencarianBinerDemo.java
text Keluaran 
target 23 -> indeks 5, langkah 3
target 70 -> indeks -1, langkah 3
n 10 -> langkah terburuk 4
n 100 -> langkah terburuk 7
n 1000 -> langkah terburuk 10
n 1000000 -> langkah terburuk 20
tengah naif: -547483648 (negatif akibat luapan)
tengah aman: 1600000000

Delapan baris keluaran menjawab dua pertanyaan sekaligus. Enam baris pertama identik dengan versi Python, termasuk 20 langkah untuk sejuta elemen, karena jumlah langkah adalah sifat algoritmanya. Tengah naif berubah menjadi -547483648 akibat luapan, sedangkan tengah aman menghitung 1600000000 dengan benar. Python tidak mengalami masalah ini karena bilangan bulatnya bebas luapan, tetapi kebiasaan menulis rumus aman tetap dipertahankan agar templatnya dapat dipindah antar bahasa tanpa penyesuaian.

Ringkasan#

  • Templat rentang tertutup menjaga invarian bahwa target selalu berada di dalam [kiri, kanan], dengan tengah yang diperiksa lalu dibuang dari rentang berikutnya.
  • Kasus terburuknya menuntut ⌊log⁡2n⌋+1\lfloor \log_2 n \rfloor + 1 langkah, terbaca dari 4 langkah untuk n=10n = 10 hingga 20 langkah untuk satu juta elemen.
  • Kondisi perulangan, batas awal, dan pembaruan batas harus konsisten dengan satu invarian, karena campuran dua invarian melahirkan elemen yang terlewat dan rentang yang macet.
  • Rumus kiri + (kanan - kiri) / 2 wajib di Java karena penjumlahan naif dapat meluap pada indeks besar, dan hasilnya berubah menjadi negatif tanpa pesan.

Referensi#