Algoritma binary search
Algoritma binary search adalah algoritma pencarian pada array/list dengan elemen terurut, yang dilakukan dengan memotong array menjadi dua bagian secara terus menerus hingga nilai yang dicari ditemukan. Nama lain dari algoritma ini adalah half-interval search, logarithmic search, dan binary chop.
Gambar berikut mengilustraikan bagaimana algoritma binary search mencari elemen bernilai 3 pada sebuah list terurut.
Penjelasan:
- List dimana pencarian dilakukan memiliki 18 elemen
- Pencarian elemen (nilai 7) sampai akhirnya ditemukan, dilakukan dalam empat iterasi sbb:
- Pada iterasi pertama, batas awal pencarian ada pada elemen dengan indeks 0, batas akhir ada pada elemen dengan indeks 17. Posisi pencarian diambil dari tengah-tengah kedua batas (17-0)/2 = 8. Pada indeks 8 ditemukan elemen bernilai 14. Nilai elemen ini lebih besar dari nilai yang dicari, oleh karena itu batas akhir pencarian digeser pada posisi pencarian saat ini dikurangi 1.
- Pada iterasi kedua batas awal dan akhir menjadi 0 dan 7, posisi tengah didapatkan pada indeks 3. Pada indeks ini ditemukan elemen bernilai 6, ini berarti bahwa batas awal perlu dinaikkan ke posisi pencarian saat ini ditambah 1.
- Pada iterasi ketiga batas awal dan akhir menjadi 4 dan dan 7, posisi tengah didapatkan pada indeks 5. Pada indeks ini ditemukan elemen bernilai 8, ini berarti batas akhir kembali diturunkan ke indeks 4 (5-1)
- Pada iterasi ke 4, batas awal dan akhir menjadi 4 dan 4, posisi tengah pada indeks 4, dan ditemukan elemen bernilai 7.
Jalankan kode berikut untuk lebih memahami urut-urutan langkah di atas