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

Belajar koding untuk pemula
Privacy Overview

This website uses cookies so that we can provide you with the best user experience possible. Cookie information is stored in your browser and performs functions such as recognising you when you return to our website and helping our team to understand which sections of the website you find most interesting and useful.