📋 Daftar Isi
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
Contoh Binary 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
Ilustrasi Binary Search
Algoritma Binary Search
- 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.
