Binary Search

Binary Search Algorithm atau Algoritma Pencarian Biner adalah salah satu algoritma pencarian yang performanya cukup baik, lebih baik daripada mencari data secara traversal.

Seperti algoritma pencarian lain, binary search juga memiliki keuntungan dan kerugian. Keuntungannya adalah proses pencarian relatif lebih cepat karena tidak semua elemen dalam array diperiksa. Adapun kerugiannya adalah binary search hanya efektif jika diterapkan terhadap array yang datanya sudah terurut. Jika elemen dalam array itu mengalami penambahan, pengubahan maupun penghapusan, maka array harus diurutkan lagi. Untuk mengurutkan data dengan cepat kita bisa menggunakan QuickSort.

Logika algoritma binary search cukup sederhana:

  1. Elemen yang akan dicari dibandingkan dengan elemen tengah dalam sebuah array
  2. Jika elemen yang dicari lebih kecil daripada elemen tengah maka ruang pencarian akan dipersempit menjadi antara elemen awal hingga elemen tengah. Sebaliknya jika elemen yang dicari lebih besar daripada elemen tengah maka ruang pencarian akan dipersempit menjadi antara elemen tengah hingga elemen akhir.
  3. Proses 2 dilakukan berulang-ulang, semakin lama ruang pencarian menjadi semakin sempit hingga akhirnya dapat diputuskan apakah elemen yang dicari ditemukan atau tidak.
  4. Jika elemen yang dicari ditemukan maka biasanya binary search akan mengembalikan posisi (index) elemen tersebut dalam array, sedangkan jika tidak maka binary search akan mengembalikan index bernilai negatif (sebagai penanda bahwa elemen yang dicari tidak ditemukan)

Berikut ini adalah contoh source code sebuah function yang mengimplementasikan binary search dalam VB.NET (harap diingat bahwa  index array dalam VB.NET  dimulai dari nol)

Function BinarySearch(ByVal arr() As String, ByVal cari As String) _
As Long
 Dim posisi As Long
 Dim tengah, akhir, awal As Long
 Dim ketemu As Boolean
 ketemu = False
 'set posisi default = -999 bila elemen yang dicari tidak ditemukan
 posisi = -999
 akhir = UBound(arr)
 awal = 0
 Do
   tengah = (akhir + awal) \ 2
   If cari = arr(tengah) Then
     ketemu = True
     posisi = tengah 'indeks array tempat elemen ditemukan
   Else
     If cari < arr(tengah) Then
       akhir = tengah - 1
     Else
       awal = tengah + 1
     End If
   End If
 Loop Until (ketemu = True) Or (akhir < awal)
 BinarySearch = posisi 'return statement
End Function

Untuk membantu anda memahami prinsip kerja binary search, visualisasi dan simulasi algoritma binary search yang ada di sini saya rasa akan cukup membantu.

Semoga bermanfaat 🙂

 

sumber gambar: http://www.gutterbucket.com
Iklan

Satu pemikiran pada “Binary Search

  1. Ping-balik: QuickSort « W H Y

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s