�ݺ�ߣ

DEFINISI PENCARIAN DALAM LARIK
 Pencarian (Searching) merupakan proses yang
fundamental dalam pemrograman.
 Proses pencarian adalah menemukan nilai
(data) tertentu di dalam sekumpulan nilai yang
bertipe sama (tipe dasar atau tipe bentukan).

 Hasil atau keluaran dari persoalan pencarian
dapat bermacam-macam, misalnya:
 Pesan bahwa x ditemukan atau tidak ditemukan
dalam larik
 Indeks elemen larik, jika x ditemukan maka simpan
indeks larik tempat x ditemukan ke dalam peubah
IDX, jika tidak terdapat dalam larik L, IDX diisi
dengan harga 0.
 Peubah boolean, jika x ditemukan maka sebuah
peubah boolean, misalnya “ketemu”, diisi dengan
nilai true, sebaliknya “ketemu” diisi dengan false.

 Algoritma yang akan dibahas di dalam Bab ini
adalah :
 Pencarian beruntun (Sequential search)
 Pencarian bagidua (Binary search)

PENCARIAN BERUNTUN (SEQUENTIAL SEARCH)
 Pencarian beruntun adalah proses membandingkan
setiap elemen larik satu persatu secara beruntun,.
 Mulai dari elemen pertama sampai elemen yang
dicari ditemukan, atau seluruh elemen sudah
diperiksa.
 Perhatikan larik L di bawah ini:
1 2 3 4 5 6

 Pendeklarasian:
Deklarasi
Const Nmaks = 100 {jumlah maksimum elemen
larik }
Type Larik : Array [1..Nmaks] of integer

 Beberapa versi algoritma pencarian beruntun:
a. Versi 1 (Tidak menggunakan peubah Boolean)
 Elemen larik L dibandingkan mulai dari elemen
L[1].
 Proses pembandingan terus dilakukan selama
elemen L[k] tidak sama dengan X dan indeks larik
belum sama dengan n.
 Pembandingan dihentikan bila L[k] = x atau indeks
larik sudah sama dengan N.

procedure cari_Indeks (input L : larik, input n, x : integer,
output idx : integer)
Deklarasi
k : integer { indeks larik }
Deskripsi
k  1
while (k < n) and (L[k] ≠ x) do
k  k + 1
endwhile
{ k = n or L[k] = x }
if L[k] = x then { x ditemukan }
Idx  k
else
Idx  0
endif

b. Versi 2 (Menggunakan Peubah Boolean)
 Peubah boolean ketemu diinisialisasi dengan nilai
false.
 Elemen larik L dibandingkan mulai dari elemen ke-
k = 1, 2, …, n. jika L[k] sama dengan X.
 Peubah ketemu diisi dengan harga true dan proses
pembandingan dihentikan.
 Sebaliknya, jika L[k] tidak sama dengan x, peubah
ketemu tetap false nilainya dan proses
pembandingan dilanjutkan untuk elemen
berikutnya.

procedure cari_Indeks (input L : larik, input n, x : integer,
output idx : integer)
Deklarasi
k : integer { indeks larik }
ketemu : boolean { true jika ditemukan, false bila tidak }
Deskripsi
k  1
while (k ≤ n) and (not ketemu) do
if L[k] = x then
ketemu  true
else
k  k + 1
endif
endwhile
{ k > N or ketemu }
if ketemu then { x ditemukan }
Idx  k
else
Idx  0
endif

PENCARIAN BAGIDUA (BINARY SEARCH)
 Pencarian bagidua adalah metode pencarian
yang diterapkan pada sekumpulan data yang
sudah terurut (terurut menaik atau terurut
menurun).
 Metode ini digunakan untuk kebutuhan
pencarian dengan waktu yang cepat.

 Misalkan indeks kiri adalah i dan indeks kanan
adalah j. pada mulanya, j =1 dan j = N
Langkah 1: Bagi dua elemen larik pada elemen tengah.
Elemen tengah adalah elemen dengan indeks k = (i+j) div
2. (elemen tengah, L[k], membagi larik menjadi dua
bagian, yaitu bagian kiri L[i..j] dan bagian kanan L[k+1..j])
Langkah 2: Periksa apakah L[k] = X. jika ya, pencarian
dihentikan karena x sudah ditemukan. Tetapi jika L[k] ≠ X,
harus ditentukan apakah pencarian akan dilakukan di
larik bagi kiri atau di bagian kanan. Jika L[k] < X, maka
pencarian dilakukan pada larik bagian kiri. Sebaliknya jika
L[k] > X, pencarian dilakukan pada larik bagian kanan.
Langkah 3: Ulangi langkah 1 sampai X ditemukan atau i >
j (yaitu, ukuran larik sudah 0)

 Ilustrasi pencarian bagidua:
Misalkan diberikan larik L dengan delapan buah
elemen yang sudah terurt menurun seperti berikut:

 Algoritma pencarian bagidua untuk larik terurut
menurun:
procedure bagi_dua1 (input L : larik, input n, x :
integer, output idx : integer)
Deklarasi
i, j : integer { indeks kiri dan
indeks kanan larik }
k : integer { indeks elemen tengah }
ketemu : boolean { true jika ditemukan,
false bila tidak }

Deskripsi
i  1
j  n
ketemu  false
while (not ketemu) and (i ≤ j) do
k  (i + j) div 2 { bagi dua larik L pada posisi ke k }
if (L[k] = x) then
ketemu  true
else
if (L[k] > x) then
i  k - 1
else
j  k + 1
endif
endif
endwhile

 Bagaimana algoritma pencarian bagidua untuk
larik terurut menaik?

�ݺ�ߣ

Sd bab 3 (pencarian)

Recommended

More Related Content

Similar to Sd bab 3 (pencarian) (6)

More from Nm Aditya Danger (7)

Sd bab 3 (pencarian)