Artikel ini merupakan lanjutan dari artikel sebelumnya tentang searching, langsung saja APA ITU BINARY SEARCH?
Adalah metode searching dengan cara mencari nilai tengah data dan membaginya menjadi dua bagian. dalam metode ini data harus terurut terlebih dahulu. Setelah itu dilakukan perbandingan untuk menentukan data berada disebelah kanan atau di sebelah kirinya, kemudian mencari setengah sisanya dengan cara yang sama kembali. Binary Search dilakukan untuk :
- Memperkecil jumlah operasi pembandingan yang dilakukan terhadap data yang ada di dalam larik (array), khususnya untuk jumlah data yang sangat besar ukurannya.
- Beban komputasi juga akan menjadi lebih kecil dikarenakan searching dilakukan dari 3 arah yaitu depan, belakang, dan tengah.
- Prinsip dasarnya yaitu 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).
Langkah langkah utamanya :
- posisi awal=1 dan posisi akhir = n.
- cari posisi data tengah dengan rumus posisi tengah = (posisi awal + posisi akhir ) dibagi 2.
- Kemudian data yang di cari dibandingkan dengan data tengah.
- Jika sama, data ditemukan, Proses selesai.
- Jika lebih kecil, proses dilakukan kembali tetapi posisi akhir dianggap sama dengan posisi tengah di kurangi 1.
- Jika lebih besar , proses dilakukan kembali tetapi posisi awal dianggap sama dengan posisi tengah di tambah 1.
- Ulangi langkah kedua hingga data ditemukan , atau tidak ditemukan.
- proses berakhir jika data ditemukan posisi awal lebih besar dari pada posisi akhir. Jika posisi awal lebih besar dari posisis akhir berarti data tidak diketemukan.
Kelebihan
- Binary search akan tepat digunakan jika dalam data yang cukup banyak
- beban komputasi lebih kecil karena pencarian dilakukan dari depan, tengah, dan belakang.
Kekurangan
- Data harus di sorting dahulu.
- Algoritma cukup rumit.
Algoritma Singkat :
L <- 0
R <- N – 1
Ketemu <- False
while (L <= R) dan ‘ Tidak Ketemu’ do
m <- (L + R) div 2
if (Data[i] = key) then ketemu <- true
if (key < Data[i] then R <- i – 1
if (key > Data[i] then L <- i + 1
end while
if (ketemu) then
m = indeks data yang di cari
if (not ketemu) then
data tidak ditemukan
