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.

Binary search, mencari nilai 7 dari list terurut. Sumber ilustrasi: Wikipedia

Penjelasan:

  1. List dimana pencarian dilakukan memiliki 18 elemen
  2. 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

You may also like...

Berikan komentar