Tugas Algoritma dan Pemrograman: Binary Search

Algoritma binary search adalah jenis algoritma bertipe devide and conquer yang diciptakan untuk mereduksi jumlah perbandingan secara drastis dengan cara menentukan batas daerah solusi lalu menyelesaikan (solve it) secara berulang (recursive) sampai data ditemukan. Syarat wajib bekerjanya algoritma binary search adalah data harus dalam kondisi berurutan agar proses pencarian bisa dilakukan.

Gambar: Proses pencarian pada Binary search

Algoritma binary search:

Tentukan batas daerah solusi awal, batas kiri = 1 dan batas kanan = jumlah data (contoh 15).
Tentukan posisi tengah antara batas kiri dan batas kanan.
Jika data tengah = data dicari, maka cetak "Data ketemu di posisi tengah", dan pencarian selesai.
Jika tidak, bandingkan lagi, jika data tengah > data dicari, maka { daerah solusi menyempit di antara batas kiri dan batas tengah } batas kanan ← tengah, jika tidak maka { daerah solusi menyempit antara batas tengah dan batas kanan } batas kiri ← tengah.
Selama batas kiri tidak berdempetan dengan batas kanan, jalankan baris ke 3, jika tidak ,maka cetak "Data tidak ketemu".
Selesai.

Gambar: Hasil running binary search

Kronologis pencarian contoh data di atas

Dicari kosakata "access" pada 15 data yang berurutan dengan posisi kiri = 1, posisi kanan = 15, sehingga didapat posisi tengah = 7, yaitu "abuse".
Karena data tengah ("abuse") < data yg dicari ("access") maka posisi bergeser, posisi kiri = 7, posisi kanan = 15, sehingga didapat posisi tengah = 10, yaitu "accent".
Karena data tengah ("accent") < data yg dicari ("access") maka posisi bergeser kembali, posisi kiri = 10, posisi kanan = 15, sehingga didapat posisi tengah = 12, yaitu "access".
Karena data tengah ("access") = data yg dicari ("access" maka cetak "data ketemu di posisi tengah" sehingga proses pencarian berhenti.
Jika posisi kiri dan posisi kanan berdempetan, maka sudah tidak ada lagi anggota himpunan solusi sehingga dapat disimpulkan bahwa data tidak ketemu.

Kode Program: VB.Net

Algoritma binary search ini sangat mangkus (efisien waktunya) karena kecepatannya meningkat secara eksponensial seiring dengan meningkatnya jumlah data. Jika jumlah data = 15, maka proses perbandingan maksimal = 4x. Jika jumlah data = 4294967296 (4 milyar) maka hanya dibutuhkan perbandingan 32 kali saja.

Berbeda dengan Algoritma Linear search yang membutuhkan siklus perbandingan yang sangat lama Jika jumlah data = 15, maka proses perbandingan rata-rata 7x , namun bila jumlah data = 4294967296 (4 milyar) maka perbandingan rata-rata sebanyak 2 milyar kali. Kompleksitas waktu rata2 algoritma linear search = 1/2 n, sedangkan kompleksitas maksimal algoritma binary search = log2 n, dimana n adalah jumlah data.

Berbeda drastiskan! Algoritma binary search ini biasanya diterapkan pada aplikasi pencarian data seperti software kamus yang pernah penulis buat. Penulis juga menjadikan topik searching ini dalam kursus pemrograman yang akan dibuka pada bulan februari 2011.