Pencarian dengan Algoritma Binary Search

Pencarian bagidua atau pencarian biner adalah metode pencarian yang diterapkan pada sekumpulan data yang sudah terurut (terurut menaik atau terurut menurun). Data yang terurut syarat mutlak penerapan algoritma ini. Salah satu keuntungan data terurut adalah memudahkan pencarian, dalam hal ini pencarian bagidua.

Misalkan indeks kiri adalah Ia dan indeks kanan adalah Ib. Kondisi awal Ia=1 dan Ib = N.
Langkah 1. Bagi dua elemen larik pada elemen tengah. Elemen tengah adalah elemen dengan indeks k = (Ia+Ib) div 2
(elemen tengah , L[k], membagi larik menjadi dua bagian, yaitu bagian kiri L[Ia..k-1] dan bagian kanan L[K+1..Ib])

Langkah 2. Periksa apakah L[k] = X.
Jika L[k] = X, pencarian dihentikan sebab X sudah ditemukan. Tetapi, jika L[k] ≠ X, harus ditentukan apakah pencarian akan dilakukan di larik bagian kiri atau di bagian kanan. Jika L[k] < X, maka pencarian dilakukan pada bagian kiri. Sebaliknya, jika L[k] > X, pencarian dilakukan pada larik bagian kanan.
Langkah 3. Ulangi langkah 1 sampai X ditemukan atau Ia > Ib (ukuran larik sudah nol).

Procedure Bagidua(input L: Larik, input N:integer, input X: integer, output IX:integer)
Algoritma
Ia <-N
Ib <-1
ketemu <-false
while (not ketemu) and (Ib > Ia) do
k <-(Ia + Ib) div 2
if (L[k] = X) then
ketemu= true
else
if (L[k] > X) then
Ia <-k
else
Ib <-k+1
endif
endif
endwhile
If (ketemu = true) then
IX <-k
else
IX <-0
endif

Contoh :
Diketehui sebuah senarai belum terurut dan bilangan yang akan dicari adalah 2 :

2

35

7

4

6

1

9

4

23

25

Penyelesaian :

1. Urutkan terlebih dahulu semua bilangan, boleh terurut menaik atau terurut menurun. Kali ini saya akan menggunakan terurut menaik sehingga diperoleh array sebagai berikut dan kemudian saya tambah dengan keterangan urutan di baris bawah.

Nilai	1	2	4	4	6	7	9	23	25	35
Indeks	1 (Ib)	2	3	4	5	6	7	8	9	10 (Ia)

2. Tentukan Indek atas (Ia) dan indek bawah (Ib). Ia adalah nilai indek terbesar dari array yaitu 10. Sedangkan Ib indek terkecik dari array yaitu 1. dan kita tetapkan bahwa saat ini ketemu=tidak ketemu.
3. Cek apakah saat ini ketemu != ketemu dan Ib < dari Ia? Jika iya maka buka elemen ke-k, dimana k adalah Ia+Ib/2 = 10+1/2= 5 (Biasanya pembulatan kebawah).
4. Sekarang periksa elemen ke-5 apakah sama dengan 2 (bilangan yang dicari)? Ternyata bukan, elemen ke-5 adalah 6.
5. Karena bukan maka periksa apakah nilai elemen ke-5 > dari 2?? Jika iya maka nilai Ia akan diubah menjadi k atau sama saja dengan Ia=k=5. Sehingga area yang dicari menjadi lebih sempit.

Nilai	1	2	4	4	6
Indeks	1 (Ib)	2	3	4	5 (Ia)

6. Cek apakah saat ini ketemu != ketemu dan Ib < dari Ia? Jika iya maka buka elemen ke-k, dimana k adalah Ia+Ib/2 = 1+5/2= 3.
7. periksa elemen ke-3 apakah sama dengan 2 (bilangan yang dicari)? Ternyata bukan, elemen ke-3 adalah 4.
8. Karena bukan maka periksa apakah nilai elemen ke-3 > dari 2?? Jika iya maka nilai Ia akan diubah menjadi  k atau sama saja dengan Ia=k=3.

Nilai	1	2	4
Indeks	1 (Ib)	2	3 (Ib)

9. Cek apakah saat ini ketemu != ketemu dan Ib < dari Ia? Jika iya maka buka elemen ke-k, dimana k adalah Ia+Ib/2 = 1+3/2= 2.
10. periksa elemen ke-2 apakah sama dengan 2 (bilangan yang dicari)? Ternyata benar. Jika benar ketemu =ketemu.
11. Cek apakah saat ini ketemu != ketemu dan Ib < dari Ia? tidak! ketemu=ketemu maka perlulangan berhenti.

Jika dilihat kembali dengan binary search elemen yang diperiksa hanya elemen ke 5, 3 dan 2. dengan tiga langkah elemen yang dicari langsung ketemu.