Algoritma Binary Search Ilustration

Algoritma pencarian bagidua atau yang disebut binary search.  Merupakan algoritma pencarian pada data terurut yang paling efficient. Dikatakan efficient karena dalam penggunaannya algoritma ini membutuhkan waktu pencarian yang cepat.

Sebagai contoh saya akan membahas tentang algoritma pencarian pada data terurut menurun dengan binary search.

Diasumsikan elemen-elemen larik sudah terurut dari besar ke kecil, selama pencarian kita memerlukan dua buah indeks larik, disini saya menggunakan larik a untuk menyebut indeks ujung kiri dan b untuk indeks ujung kanan. Pertama kita inisialisasi a dengan 1 dan b dengan n.

Langkah pertama yaitu bagi kedua elemen larik pada elemen tengah. Elemen tengah adalah elemen dengan indeks k=(a+b) div 2. Selanjutnya periksa apakah L[k]=x. L merupakan nama lariknya, jika L[k]=x, pencarian berhenti atau selesai karena x sudah ditemukan. Tetapi jika L[k]≠x, kita harus menentukan apakah pencarian akan dilakukan dilarik bagian kiri atau dibagian kanan. Jika L[k]<x, maka pencarian dilakukan pada larik bagian kiri, begitu sebaliknya jika L[k]>x, pencarian dilakukan lagi pada larik bagian kanan. Lalu ulangi langkah 1 hingga x ditemukan atau a>b (ukuran larik sudah nol).

Berikut ilustrasi binary search: dimisalkan ada larik L dengan delapan buah elemen yang sudah terurut menurun

9

7

6

4

3

2

1

a=1            2                    3                    4                    5                    6                        b=7

Langkah I:

Kita bagi larik L menjadi dua bagian dengan cara a=1 dan b=7, k=(1+7) div 2 = 4

9

7

6

4

3

2

1

a=1                  2                    3                    4                    5                    6                        b=7

Misalkan elemen yang dicari adalah x = 6.

Langkah II: Bandingkan L[4] dengan 6, apakah L[4]=6 ? Tidak, maka dari itu kita harus menentukan apakah pencarian akan dilakukan di bagian kiri atau dibagian kanan dengan pemeriksaan sebagai berikut: karena L[4]<6 maka pencarian dilakukan pada bagian kiri dengan a=1 dan b=3

9

7

6

a=1                                    2                                  b=3

                                    kiri

Langkah III: Pembagian a=1 dan b=3, k=(1+3) div 2 = 2.

9

7

6

a=1                                    2                                  b=7

            kiri                                                       kanan

Langkah IV: lakukan pemandingan kembali antara L[2] dengan 6, ternyata L[2]>6 sehingga pencarian dilakukan pada larik bagian kanan dengan a=7 dan b=7.

6

        a=b=7

Langkah V: pembagian a=7 dan b=7, k=(7+7) div 2 = 7.

6

            7

Langkah VI: bandingkan L[7] dengan 6, apakah L[7]=6 ? Ya ! Pencarian selesai, x ditemukan.