Searching ( Pencarian )
Pencarian (searching) merupakan proses yang fundamental dalam
pengolahan data. Proses pencarian adalah menemukan nilai (data) tertentu
didalam sekumpulan data yang bertipe sama. Data dapat disimpan secara
temporer dalam memori utama atau disimpan secara permanen dalam
memori sekunder. Dalam memori utama data disimpan dalam bentuk
array(larik) sedangkan dalam memori sekunder dalam bentuk file(arsip).
Pencarian
elemen dalam larik disebut juga pencarian internal, sedangkan pencarian
data yang disimpan dalam memori sekunder disebut juga pencarian
eksternal.
Persoalan Pencarian
Diberikan sebuah larik L yang sudah terdefinisi elemen-elemennya, x
adalah elemen yang bertipe sama dengan elemen larik L. Carilah x didalam
larik L.
Hasil dari proses pencarian dapat bermacam-macam :
a) Pencarian hanya memeriksa keberadaan x. Keluaran yang diinginkan misalnya
berupa pesan bahwa x
ditemukan atau tidak ditemukan.
contoh :
write(x,’ditemukan’) atau
write(x,’tidak ditemukan’)
b) Hasil pencarian adalah indeks elemen larik. Jika x ditemukan maka indek elemen
larik tempat x berada diisikan kedalam idx. Jika x tidak terdapat didalam larik L
maka idx diisi dengan nilai khusus misalnya -1.
contoh :
D 35 15 60 70 25 10 12
0 1 2 3 4 5 6
Misalkan x=70, maka idx=3. Tetapi jika x=100, maka idx=-1
c) Hasil pencarian adalah sebuah nilai boolean yang menyatakan status hasil
pencarian. Jika x ditemukan
maka sebuah variabel bertipe boolean misalnya ketemu diisi dengan nilai true, jika
sebaliknya maka ketemu
diisi dengan false.
I. Pencarian Beruntun (sequential search)
Metode pencarian beruntun adalah proses membandingkan setiap elemen larik satu
persatu secara beruntun,mulai dari elemen pertama sampai dengan elemen yang
dicari ditemukan atau seluruh elemen sudah ditemukan.
I. a. Versi 1 (Pembandingan elemen dilakukan diawal pengulangan)
(1). Hasil pencarian : sebuah variabel boolean bernilai true bila x ditemukan atau false
bila x tidak
ditemukan.
Sudah ada array 1D yang dideklarasikan dengan int L[11] dan sudah ada isinya dengan
ilustrasi sebagai
berikut :
n
0 1 2 3 4 5 6 7 8 9 10
12 17 10 5 15 25 11 7 25 16 19
Misal elemen yang akan dicari adalah x.
Setiap elemen larik L dibandingkan dengan x mulai dari elemen pertama L[0]. Aksi
pembandingan
dilakukan selama indek larik i belum melebihi n dan L[i] belum sama dengan n. Aksi
pembandingan dihentikan jika L[i] = x atau i = n. Elemen terakhir L[n] diperiksa secara
khusus.
DEKLARASI
i : integer
DESKRIPSI
I0
while (i < n) and (L[i] x) do
ii+1
endwhile
if L[i] = x then
ketemu true
else
ketemu false
endif
(2). Hasil Pencarian : indek elemen larik yang
mengandung x Setiap elemen larik L dibandingkan
dengan x mulai dari elemen pertama L[0]. Aksi
pembandingan dilakukan selama indek larik i belum
melebihi n dan L[i] belum sama dengan n. Aksi
pembandingan dihentikan jika L[i] = x atau i = n. Elemen
terakhir L[n] diperiksa secara khusus. Keluaran yang
LarikInt,input n : integer, input x : integer
output idx : integer)
DEKLARASI
i : integer
DESKRIPSI
i0
while (i < n) and (L[i] x) do
i i + 1
endwhile
if L[i] = x then
idx i
else
idx -1
endif
Kinerja metode pencarian berurutan
Metode Pencarian Beruntun berjalan lambat. Waktu pencarian sebanding dengan
jumlah elemen larik. Misal larik berukuran n elemen maka pada kasus dimana x tidak
terdapat dalam larik atau x ditemukan pada elemen terakhir, maka harus dilakukan
perbandingan sebanyak n kali. Jadi waktu pencarian dengan metode pencarian
beruntun sebanding dengan n.
III. Metode Pencarian Beruntun pada larik terurut
Larik yang jumlah elemen-elemennya terurut dapat meningkatkan kinerja algoritma
pencarian beruntun.
Contoh :
(a). Diberikan larik L tidak terurut :
13 16 14 21 76 15
untuk mencari 15, dibutuhkan perbandingan sebanyak 6 kali.
(b). Misalkan larik L diatas sudah diurut naik :
13 14 15 16 21 76
untuk mencari 15, dibutuhkan perbandingan hanya 3 kali
Prosedur berikut adalah algoritma pencarian beruntun pada larik yang terurut menaik,
yang merupakan modifikasi dari algoritma sebelumnya dengan merubah L[i] tdk sama
dengan x menjadi L[i] <x.