My first Magazine pemrograman-kompetitif-dasar | Page 36

3 Pencarian dan Pengurutan
Algoritma 10 Contoh Kode Pencarian Sederhana.
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
procedure SEARCH (h, X)
hasil ← 0
for i ← 1, N do
if (h[i] = X) then
hasil ← i
break
end if
end for
if (hasil = 0) then
print "beri hadiah lain"
else
print hasil
end if
end procedure
. Artinya belum ditemukan
Algoritma pencarian dengan membandingkan elemen satu per satu semacam ini disebut
dengan sequential search atau linear search . Jika ada N elemen pada daftar yang perlu dicari,
maka paling banyak diperlukan N operasi perbandingan. Dalam kompleksitas waktu, performa
algoritma sequential search bisa dinyatakan dalam O(N).
3.1.2 Binary Search
Apakah ada algoritma pencarian yang lebih baik? Misalkan Anda diberikan Kamus Besar
Bahasa Indonesia (KBBI) yang mengandung 90.000 kata. Anda kemudian ingin mencari definisi
suatu kata pada KBBI. Dengan sequential search perlu dilakukan paling banyak 90.000 operasi.
Apakah kita sebagai manusia melakukan perbandingan sampai 90.000 kata?
Ternyata, kita tidak perlu mencari kata satu per satu, halaman demi halaman, sampai 90.000
kata. Bahkan, kita dapat mencari arti suatu kata cukup dalam beberapa perbandingan, yang jauh
lebih sedikit dari 90.000. Bagaimana hal ini bisa terjadi?
Sifat Khusus: Terurut
KBBI memiliki sebuah sifat khusus, yaitu terurut berdasarkan abjad. Dengan sifat ini,
kita bisa membuka halaman tengah dari KBBI, lalu periksa apakah kata yang kita cari ada pada
halaman tersebut.
Misalkan kata yang kita cari berawalan ’W’. Jika halaman tengah hanya menunjukkan daftar
kata dengan awalan ’G’. Jelas bahwa kata yang kita cari tidak mungkin berada di separuh
pertama kamus. Ulangi hal serupa dengan separuh belakang kamus, buka bagian tengahnya dan
bandingkan. Dengan cara ini, setiap perbandingan akan mengeliminasi separuh rentang pencarian.
Pencarian seperti ini disebut dengan binary search .
Analisis Binary Search
Misalkan terdapat sebuah daftar berisi N elemen, dan kita perlu mencari salah satu elemen.
Banyaknya operasi maksimal yang dibutuhkan sampai suatu elemen bisa dipastikan keberada-
annya sama dengan panjang dari barisan [N, N 2 , N 4 , N 8 , ..., 2, 1] yakni sebesar dlog 2 Ne, sehingga
kompleksitasnya O(log N).
26