My first Magazine pemrograman-kompetitif-dasar | Page 38

3 Pencarian dan Pengurutan
• Jika ternyata X kurang dari h[tengah], artinya X tidak mungkin berada pada rentang [tengah,
kanan].
• Dengan demikian, rentang pencarian kita yang baru adalah [kiri, tengah-1].
• Hal yang serupa juga terjadi ketika X lebih dari h[tengah], rentang pencarian kita menjadi
[tengah+1, kanan].
• Tentu saja jika X sama dengan h[tengah], catat posisinya dan pencarian berakhir.
• Untuk kasus X tidak ditemukan, pencarian akan terus dilakukan sampai kiri > kanan, yang
artinya rentang pencarian sudah habis.
Ilustrasi Eksekusi Binary Search
Sebagai contoh, misalkan Anda ingin mencari angka 3 dari suatu array [1, 1, 3, 5, 5, 6, 7].
Gambar 3.1 sampai Gambar 3.6 mengilustrasikan proses binary search dari awal sampai akhir.
1 1 3 5 5 6 7
kanan
kiri
Gambar 3.1: Tahap 1: Mulai dengan menginisiasi variabel kiri dan kanan pada kedua ujung array .
1 1 3 5 5 6 7
kanan
kiri
Gambar 3.2: Tahap 2: Temukan indeks tengah yaitu nilai tengah dari kiri dan kanan. Kemudian
lakukan perbandingan nilai tengah dengan nilai yang ingin dicari.
1 1 3 5 5 6 7
kiri
kanan
Gambar 3.3: Tahap 3: Karena 5 > 3, maka geser kanan menjadi tengah − 1.
1 1 3 5 5 6 7
kiri
kanan
Gambar 3.4: Tahap 4: Temukan lagi indeks tengah yaitu nilai tengah dari kiri dan kanan dan
bandingkan nilainya dengan nilai yang dicari.
1 1 3 5 5 6 7
kanan
kiri
Gambar 3.5: Tahap 5: Karena 1 < 3, maka geser kiri menjadi tengah + 1.
28