Searching
1 Sequential Search
Sequential Search adalah Proses
menemukan data dari array yang ditinjau dengan cara menelusuri satu persatu
elemen array mulai dari elemen array pertama sampai data yang dicari ditemukan
atau sampai seluruh elemen array ditelusuri.
a. Sequential Search Tanpa
Boolean
-
Tanpa Sentinel
Mis. diberikan data sebagai berikut:
5
|
1
|
9
|
4
|
2
|
1
|
2
|
3
|
4
|
5
|
Angka
Data yang dicari : 9
Angka(1) = 9? F
Angka(2) = 9? F
Angka(3) = 9? T
Maka data yang dicari ditemukan pada indeks ke-3
Peseudo-Code
Procedure SeqSearchTanpaSentinel(Input nama_array:tipe_array)
{I.S. : elemen array [1..maks_array] sudah terdefinisi}
{F.S. : menampilkan data yg dicari ditemukan atau tidak
ditemukan}
Kamus:
i :
integer
data_cari :
tipedata
Algoritma:
input(data_cari)
i←1
while(nama_array (i) ≠
data_cari) and (i <
maks_array) do
i
←i + 1
endwhile
if (nama_array(i) = data_cari)
then
output(data_cari,’ ditemukan
pada indeks ke-’,i)
else
output(data_cari,’
tidak ditemukan’)
endif
EndProcedur
Dengan
Sentinel
Mis. diberikan data sebagai berikut:
5
|
1
|
9
|
4
|
2
|
1
|
2
|
3
|
4
|
5
|
9
|
6
|
<== Sentinel
Angka
Data yang dicari : 9
- Tempatkan data yang dicari pada sentinel
- Telusuri array seperti sequential
search tanpa sentinel, jika data ditemukan pada sentinel, maka data yang dicari
tidak ada/tidak ditemukan, tapi jika data yang dicari ditemukan bukan pada
sentinel, maka data yang dicari ditemukan.
Peseudo-Code
Procedure SeqSearchSentinel(Input nama_array:tipe_array)
{I.S. : elemen array [1..maks_array] sudah terdefinisi}
{F.S. : menampilkan data yg dicari ditemukan atau tidak
ditemukan}
Kamus:
i :
integer
data_cari :
tipedata
Algoritma:
input(data_cari)
i←1
nama_array(maks_array
+ 1) ← data_cari
while (nama_array (i) ≠
data_cari) do
i
← i + 1
endwhile
if (i < maks_array+1)
then
output(data_cari,’ ditemukan
pada indeks ke-’,i)
else
output(data_cari,’
tidak ditemukan’)
endif
EndProcedure
b. Sequential Search Dengan
Boolean
Mis. diberikan data sebagai berikut:
5
|
1
|
9
|
4
|
2
|
1
|
2
|
3
|
4
|
5
|
Angka
Data yang dicari : 9
Proses pencariannya sama seperti proses pencarian pada
metode sequential search lainnya, hanya saja melibatkan sebuah variabel lain yg
bertipe Boolean.
Peseudo-Code
Procedure seq_search_boolean (Input nama_array:tipe_array)
{I.S. : elemen array [1..maks_array] sudah terdefinisi}
{F.S. : menampilkan data yg dicari ditemukan atau tidak
ditemukan}
Kamus:
i : integer
ketemu : boolean
data_cari :
tipedata
Algoritma:
input(data_cari)
i ←1
ketemu ← false
while (not ketemu) and (i ≤ maks_array) do
if (nama_var_array(i) =
data_cari)
then
ketemu ← true
else
i ← i + 1
endif
endwhile
if (ketemu)
then
output(data_cari,’ ditemukan
pada indeks ke-’,i)
else
output(data_cari,’
tidak ditemukan’)
endif
EndProcedure
Binary Search
Proses pencarian dengan
cara membagi larik menjadi 2 bagian (bagian kiri dan bagian kanan), dan
mengecek data diposisi tengah apakah sama atau tidak dengan data yg dicari,
jika tidak proses pencarian akan dilanjutkan ke larik bagian kiri atau bagian
kanan.
Mis. diberikan data
sebagai berikut:
3
|
7
|
12
|
15
|
29
|
1
|
2
|
3
|
4
|
5
|
Angka
Data yang dicari : 7
Catatan : data harus sudah terurut
Langkah 1 : bagi larik menjadi 2 bagian untuk mencari posisi
tengah (k) dengan cara indeks atas (Ia) dijumlahkan dengan indeks bawah (Ib)
lalu dibagi 2.
k = (Ia + Ib) div 2
= (1 + 5) div 2
= 3
3
|
7
|
12
|
15
|
29
|
1
|
2
|
3
|
4
|
5
|
la k lb
Bag.
Kiri Bag.
Kanan
Langkah 2 : periksa data di
posisi tengah larik (12), lalu bandingkan apakah sama atau tidak(12 = 7? F),
karena tidak sama maka akan diperiksa apakah data di posisi tengah lebih kecil
dari data yang dicari (12 < 7 ? F) karena lebih besar maka pencarian
dilanjutkan ke bagian kiri dengan cara menarik Indeks bawah ke kiri (Ib = k –
1)
Hitung kembali
titik tengah dari Larik yang ditinjau (didapat
k = 1)
Langkah 3 :
ulangi langkah 1 s/d langkah 2
sampai data ditemukan atau sampai harga Ia > Ib
Angka 7
ditemukan pada indeks ke-2, dan pada looping ke-3
Illustrasi Binary Search
Mis. Dicari
angka 7 menggunakan Binary Search
- Angka 7 ditemukan pada indeks
ke-2
-
Data yang dicari ditemukan pada
looping ke-3, dengan harga
Ia = 2 dan Ib = 2
Peseudo-Code
Procedure binary_search (Input nama_array :
tipe_array)
{I.S. : elemen
array [1..maks_array] yg terurut secara ascending sudah terdefinisi}
{F.S. : menampilkan
data yg dicari ditemukan atau tidak ditemukan}
Kamus:
Ia, Ib, k
: integer
{Ia=indeks bawah, Ib=indeks atas, k=posisi tengah}
ketemu
: boolean
data_cari
: tipedata
Algoritma:
input(data_cari)
Ia ← 1
Ib ←maks_array
ketemu ← false
while
(not ketemu) and (Ia ≤ Ib) do
k ← (Ia + Ib) div 2
if (nama_var_array(k) = data_cari)
then
ketemu ← true
else
if (nama_var_array(k)
< data_cari)
then
Ia
← k + 1
else
Ib
← k – 1
endif
endif
endwhile
if
(ketemu)
then
output(data_cari,’ ditemukan pada indeks ke-’,k)
else
output(data_cari,’
tidak ditemukan’)
endif
EndProcedure
Referensi
1. Tati Haryati. 2015. Algoritma dan Pemrograman, Bandung, UNIKOM.