Struktur Data dan Algoritma Pencarian Biner

Pencarian biner adalah algoritma pencarian cepat dengan kompleksitas run-time Ο (log n). Algoritma pencarian ini bekerja berdasarkan prinsip divide and conquer. Agar algoritme ini berfungsi dengan baik, pengumpulan data harus dalam bentuk yang diurutkan.

Pencarian biner mencari item tertentu dengan membandingkan item paling tengah dari koleksi. Jika terjadi kecocokan, maka indeks item dikembalikan. Jika item tengah lebih besar dari item, maka item tersebut dicari di sub-larik di sebelah kiri item tengah. Jika tidak, item dicari di sub-larik di sebelah kanan item tengah. Proses ini berlanjut pada sub-larik juga sampai ukuran sub larik berkurang menjadi nol.

Bagaimana Pencarian Biner Bekerja?

Agar pencarian biner berfungsi, array target wajib diurutkan. Kita akan mempelajari proses pencarian biner dengan contoh gambar. Berikut ini adalah array yang diurutkan dan mari kita asumsikan bahwa kita perlu mencari lokasi nilai 31 menggunakan pencarian biner.

Pertama, kita akan menentukan setengah dari larik dengan menggunakan rumus ini -

mid = low + (high - low) / 2

Ini dia, 0 + (9 - 0) / 2 = 4 (nilai integer 4,5). Jadi, 4 adalah tengah larik.

Sekarang kita bandingkan nilai yang disimpan di lokasi 4, dengan nilai yang sedang dicari, yaitu 31. Kita temukan bahwa nilai di lokasi 4 adalah 27, yang tidak sama. Karena nilainya lebih besar dari 27 dan kita memiliki array yang diurutkan, maka kita juga tahu bahwa nilai target harus berada di bagian atas array.

Kami mengubah rendah ke pertengahan + 1 dan menemukan nilai tengah baru lagi.

low = mid + 1
mid = low + (high - low) / 2

Pertengahan baru kami adalah 7 sekarang. Kami membandingkan nilai yang disimpan di lokasi 7 dengan nilai target kami 31.

Nilai yang disimpan di lokasi 7 bukanlah kecocokan, melainkan lebih dari apa yang kita cari. Jadi, nilainya harus di bagian bawah dari lokasi ini.

Oleh karena itu, kami menghitung lagi tengahnya. Kali ini jam 5.

Kami membandingkan nilai yang disimpan di lokasi 5 dengan nilai target kami. Kami menemukan bahwa itu cocok.

Kami menyimpulkan bahwa nilai target 31 disimpan di lokasi 5.

Pencarian biner membagi dua item yang dapat dicari dan dengan demikian mengurangi jumlah perbandingan yang akan dibuat menjadi angka yang sangat sedikit.

Pseudocode

Pseudocode dari algoritma pencarian biner akan terlihat seperti ini -

Procedure binary_search
   A ← sorted array
   n ← size of array
   x ← value to be searched

   Set lowerBound = 1
   Set upperBound = n 

   while x not found
      if upperBound < lowerBound 
         EXIT: x does not exists.
   
      set midPoint = lowerBound + ( upperBound - lowerBound ) / 2
      
      if A[midPoint] < x
         set lowerBound = midPoint + 1
         
      if A[midPoint] > x
         set upperBound = midPoint - 1 

      if A[midPoint] = x 
         EXIT: x found at location midPoint
   end while
   
end procedure

Untuk mengetahui tentang implementasi pencarian biner menggunakan array dalam bahasa pemrograman C, silahkan klik disini .