fbpx

Struktur Data : Binary Search

Binary Search (pencarian biner) hanya bisa diterapkan pada sekumpulan data yang sudah terurut (terurut menaik atau menurun).

Contoh data yang sudah terurut banyak ditemukan pada kehidupan sehari-hari:

  • Data kontak telepon di HP terurut dari nama A sampai Z
  • Data pegawai diurut berdasarkan nomor induk pegawai dari kecil ke besar
  • Data mahasiswa diurutkan berdasarkan NIM
  • Kata-kata di dalam kamus diurut dari A sampai

Keuntungan data yang terurut adalah memudahkan pencarian.

Pada setiap kali pencarian, array dibagi dua menjadi dua bagian yang berukuran sama (atau beda selisih 1 elemen). Pada setiap pembagian, elemen tengah M diperiksa apakah sama dengan X. Pada worst case scenario, yaitu pada kasus X tidak terdapat di dalam array, array dibagi sejumlah ยฒlog(N) kali, sehingga jumlah pemeriksaan yang dilakukan juga sebanyak ยฒlog(N) kali. Jika jumlah elemen 1000, pembagian array yang dilakukan adalah ยฒlog(1000) =3 kali. Jumlah pemeriksaan elemen array juga 3 kali. Untuk data terurut, algoritma binary search lebih cepat dibandingkan sequential search

Misal untuk mencari arti kata tertentu dalam kamus Bahasa Inggris, kita tidak perlu membuka kamus itu dari halaman awal sampai akhir satu per satu:

  • Pertama Kamus tersebut kita bagi dua di tengah-tengah.
  • Jika yang dicari tidak ada di pertengahan, kita cari lagi di belahan kiri atau kanan dengan membagi dua lagi belahan tersebut.
  • Begitu seterusnya sampai kata yang dicari ketemu
  • Kita memerlukan dua buah indeks pada Array A yaitu indeks terkecil dan indeks terbesar (Misal L dan H). Umumnya L=0 dan H=N
  • Langkah 1: bagi dua elemen array pada elemen tengah. Elemen tengah adalah elemen dengan indeks M = (L+H) / 2
  • Elemen tengah array A[M] membagi array membagi dua bagian, yaitu bagian kiri Array A[L..M-1] dan bagian kanan Array A[M+1..H]
  • Langkah 2: periksa apakah A[M] = X. Jika Ya, maka pencarian dihentikan (data ditemukan). Jika tidak, jika A[M] < X maka pencarian dilakukan pada array bagian kiri. Jika A[M] > X maka pencarian dilakukan pada array bagian kanan.
  • Langkah 3: Ulangi langkah 1-2 sampai X ditemukan atau L > H (ukuran array sudah nol!)

Contoh:

Misal ada array A dengan 8 elemen yang berurutan menurun. Data yang dicari adalah X = 18.

Langkah 1: L=0 dan H=7, maka indeks elemen tengah M=(0+7)/2=3

Langkah 2: A[3] = 18? Ya! (X ditemukan, pencarian dihentikan)


Materi Lengkap

Silakan baca juga beberapa artikel menarik kami tentang Searching, daftar lengkapnya adalah sebagai berikut.


Tonton juga video pilihan dari kami berikut ini

Bagikan ke teman-teman Anda

Contact Us

How to whitelist website on AdBlocker?

How to whitelist website on AdBlocker?

  1. 1 Click on the AdBlock Plus icon on the top right corner of your browser
  2. 2 Click on "Enabled on this site" from the AdBlock Plus option
  3. 3 Refresh the page and start browsing the site
error: Content is protected !!
Up