Konsep Binary Search

Binary search adalah sebuah algoritma pencarian dengan cara membagi data menjadi dua bagian setiap kali terjadi proses pencarian untuk menemukan nilai tertentu dalam sebuah larik (array) linear. Sebuah pencarian biner mencari nilai tengah (median), melakukan sebuah pembandingan untuk menentukan apakah nilai yang dicari ada sebelum atau sesudahnya, kemudian mencari setengah sisanya dengan cara yang sama. Pencarian Biner (Binary Search) dilakukan untuk :

• Memperkecil jumlah operasi pembandingan yang harus dilakukan antara data yang dicari dengan data yang ada di dalam tabel, khususnya untuk jumlah data yang sangat besar ukurannya.
• Beban komputasi juga lebih kecil karena pencarian dilakukan dari depan, belakang, dan tengah.
• Prinsip dasarnya adalah melakukan proses pembagian ruang pencarian secara berulang-ulang sampai data ditemukan atau sampai ruang pencarian tidak dapat dibagi lagi (berarti ada kemungkinan data tidak ditemukan).
• Syarat utama untuk pencarian biner adalah data di dalam tabel harus sudah terurut.

Kekurangan binary search yaitu data harus disorting dahulu dan Algoritma lebih rumit. Berikut ilustrasi pencarian menggunakan binary search dengan bantuan tabel. Misalkan kita mempunyai data sebagai berikut : {-5, -3, -1, 0, 1, 3, 5, 7}. Data yang kita cari adalah 5. Untuk menyelesaikan soal diatas, maka diselesaikan dengan cara berikut :

Diketahui nilai kiri=0 (nilai awal array) dan nilai kanan = 8. Rumus posisi tengah adalah (kanan + kiri)/2. Jadi Nilai tengah pada langkah pertama yaitu (8+0)/2=4. Jika dimasukkan kedalam tabel akan menunjuk nilai 0 (berwarna orange). Kemudian dibandingkan dengan nilai yang dicari (3), karena nilai yang dicari lebih besar dari data ditengah maka pencarian di alihkan ke sebelah kanan dengan batas kiri (awal pencarian) merupakan nilai tengah yakni 4.

Nilai tengah pada langkah kedua yaitu (8+4)/2=6. Jika dimasukkan ke dalam tabel maka akan menunjuk nilai 3 (berwarna orange). Kemudian dibandingkan lagi dengan nilai yang dicari (5), karena nilai yang dicari masih lebih besar dari nilai tengah, maka pencarian dialihkan lagi ke kanan dengan batas kiri (awal pencarian) merupakan nilai tengah yakni 6.

Nilai tengah pada langkah ketiga yaitu (8+6)/2=7. Jika dimasukkan ke dalam tabel maka akan menunjuk nilai 5 (berwarna orange). Kemudian dibandingkan lagi dengan nilai yang dicari (5), setelah dibandingkan nilainya sama, maka pencarian selesai dengan keterangan data ditemukan.

Untuk lebih jelasnya lagi perhatikan algoritma deskriptif binary search berikut :

1. Input seluruh data kedalam array
2. Input data yang dicari
3. Tentukan nilai kiri, kanan, dan tengah dengan rumus :

1. Kiri sama dengan nol
2. Kanan lebih kecil dari jumlah data
3. Tengah sama dengan hasil kanan dikurangi hasil kiri dibagi dua.

4. Jika elemen tengah tidak sama dengan data yang dicari, maka :

1. Jika elemen tengah lebih besar dari data yang dicari, maka pencarian dilakukan pada setengah array pertama. Caranya dengan menggunakan perintah kiri sama dengan tengah ditambah satu.
2. Jika elemen tengah lebih kecil dari data yang dicari, maka pencarian dilakukan pada setengah array berikutnya. Caranya dengan menggunakan perintah kanan sama dengan tengah dikurangi satu.
3. Tengah sama dengan kiri ditambah (kanan - kiri) dibagi dua.

5. Jika elemen tengah sama dengan data yang dicari, maka data ditemukan. Sedangkan jika elemen tengah tidak sama dengan data yang dicari, maka data tidak ditemukan.

Untuk penerapan, binary search bisa dibuat dibeberapa bahasa pemograman. Berikut bahasa pemgoraman yang pernah dicoba untuk penerapan binary search :

• C++

Referensi :

kazwini13.wordpress.com

dharmaatmaja.wordpress.com

Posted in: Binary Search