My first Magazine pemrograman-kompetitif-dasar | Page 37

3.1 Pencarian
Perhatikan Tabel 3.1 untuk membandingkan banyaknya operasi yang dibutuhkan untuk nilai
N tertentu.
Tabel 3.1: Perbandingan sequential search dan binary search .
N
Sequential Binary
50
50
6
100
100
7
150
150
8
200
200
8
250
250
8
300
300
9
Seperti yang terlihat, binary search jauh lebih cepat dari linear search . Bahkan untuk N = 10 6 ,
binary search hanya membutuhkan maksimal 20 operasi.
Implementasi Binary Search
Terdapat bermacam cara implementasi binary search . Salah satunya seperti yang dicon-
tohkan pada Algoritma 11. Pada algoritma ini, kita akan mencari X pada array h. Tentu kita
asumsikan bahwa h sudah terurut.
Algoritma 11 Algoritma binary search .
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
procedure B INARY S EARCH (h, X)
hasil ← 0
kiri ← 1
kanan ← N
while ((kiri ≤ kanan) ∧ (hasil = 0)) do
tengah ← (kiri + kanan) div 2
if (X < h[tengah]) then
kanan ← tengah − 1
else if (X > h[tengah]) then
kiri ← tengah + 1
else
hasil ← tengah
end if
end while
if (hasil = 0) then
print "beri hadiah lain"
else
print hasil
end if
end procedure
. Artinya belum ditemukan
Berikut adalah cara kerja dari Algoritma 11:
• Variabel kiri dan kanan menyatakan bahwa rentang pencarian kita ada di antara [kiri, kanan].
Nilai X mungkin ada di dalam sana.
• Kita mengambil nilai tengah dari kiri dan kanan, lalu periksa apakah X sama dengan
h[tengah].
27