Algoritma Binary Search [PDF]

Citation preview

Hardiyanto – 2015 http://www.neotrik.ga/ Pengertian Binary search adalah algoritma pencarian untuk data yang terurut. Pencarian dilakukan dengan cara menebak apakah data yang dicari berada ditengah-tengah data, kemudian membandingkan data yang dicari dengan data yang ada ditengah. Bila data yang ditengah sama dengan data yang dicari, berarti data ditemukan. Namun, bila data yang ditengah lebih besar dari data yang dicari, maka dapat dipastikan bahwa data yang dicari kemungkinan berada disebelah kiri dari data tengah dan data disebelah kanan data tengah dapat diabai. Upper bound dari bagian data kiri yang baru adalah indeks dari data tengah itu sendiri. Sebaliknya, bila data yang ditengah lebih kecil dari data yang dicari, maka dapat dipastikan bahwa data yang dicari kemungkinan besar berada disebelah kanan dari data tengah. Lower bound dari data disebelah kanan dari data tengah adalah indeks dari data tengah itu sendiri ditambah 1. Demikian seterusnya



Keunggulan Binary Search Keunggulan utama dari algoritma binary search adalah kompleksitas algoritmanya yang lebih kecil daripada kompleksitas algoritma sequential search. Hal ini menyebabkan waktu yang dibutuhkan algoritma binary search dalam mencari sebuah record dalam sebuah tabel lebih kecil daripada waktu yang dibutuhkan algoritma sequential search. 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.







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, misalkan terurut menaik.



Hardiyanto – 2015 http://www.neotrik.ga/ Program



Hardiyanto – 2015 http://www.neotrik.ga/ Hasil



Flowchart Analisis Program Nama program binary search, menggunakan variabel arr sebagai array dengan tipe data integer dan di batasi dari 1 sampai 100. Variabel i, j, temp, kiri, tengah, kanan, cari, x sebagai integer dan variabel ketemu sebagai boolean. Program meminta user memasukkan banyak data dan dibaca sebagai x. Kemudian memulai looping sebanyak x kali untuk mengurutkan data dengan buble short.