algoritma dan pemrograman 2 modul 51

ALGORITMA DAN PEMROGRAMAN 2Modul 5Oleh: Anis Cherid, M.T.I. PENCARIAN (SEARCHING)

Operasi pencarian adalah operasi untuk menemukan sebuah nilai (data) di

dalam sekumpulan nilai yang bertipe sama [RIN01]. Untuk menemukan nilai yang

kita cari, instruksi yang paling penting yang harus dilakukan adalah memeriksa jika

nilai yang kita cari sama dengan salah satu nilai dalam kumpulan nilai yang

dimaksud. Metode pencarian yang bisa kita pergunakan tergantung dari:

1. Bagaimana urutan nilai-nilai di dalam kumpulan nilai.

2. Bagaimana struktur data yang dipergunakan untuk menyusun nilai-nilai

tersebut.

Kita dapat mempergunakan metode pencarian beruntun atau linear (sequential

search atau linear search) jika:

1. Nilai-nilai tersebut belum berurutan.

2. Nilai-nilai tersebut sudah berurutan, tetapi struktur data yang dipergunakan

untuk menyimpan nilai-nilai tersebut adalah senarai berkait (linked list, akan

dibahas dalam kuliah-kuliah mendatang).

Kita dapat mempergunakan baik metode pencarian beruntun (sequential) maupun

metode pencarian biner (binary search), jika:

1. Nilai-nilai tersebut sudah tersusun secara berurutan, dan

2. Nilai-nilai tersebut disusun ke dalam bentuk larik (array) atau struktur data

sejenis yang masing-masing nilai tersimpan dalam bagian-bagian yang

mempunyai indeks yang unik dan indeksnya berurutan dari yang paling kecil

hingga yang paling besar (bersifat ordinal).

1. Pencarian Beruntun (Sequential Search) atau Pencarian Linear (Linear

Search)

Contoh 1

Ouput:

1. Pada layar komputer ditampilkan nilai dari 100 elemen array yang bertipe

integer serta nilai bersifat acak dan berkisar di antara 1 dan 1000.

2. Kemudian pada layar komputer ditampilkan pesan yang meminta operator

memasukkan nilai yang dicari.

PUSAT PENGMBANGAN BAHAN AJAR –UMB Anis Cherid, M.T.I.Alogaritma Dan Pemrograman II

3. Jika nilai yang dimaksud tidak ditemukan, pada layar komputer akan

ditampilkan pesan 'Nilai tidak ditemukan'. Jika nilai tersebut berhasil

ditemukan, pada layar komputer akan ditampilkan pesan 'Nilai ditemukan

pada elemen ke X', dengan X adalah indeks elemen array tempat

tersimpannya array tersebut.

Input:

1. Array bertipe integer yang terdiri dari 100 elemen.

2. Nilai yang dimasukkan oleh operator untuk dicari di dalam array.

Program yang dibutuhkan untuk menghasilkan output di atas adalah sebagai berikut:

program Cari_Dalam_Array;var

kumpulanNilai : array [1..100] of integer;nilaiDicari, indeks, i : integer;

label 9999;begin

{Mengisi 100 elemen array dengan nilai acak dan menampilkannya}randomize;for i:= 1 to 100 dobegin

kumpulanNilai[i] := random(999)+1;write(kumpulanNilai[i], ' ');

end;writeln;

{Meminta operator memasukkan nilai yang dicari}writeln ('Silakan ketikkan nilai yang dicari: ');readln (nilaiDicari);

{Mencari nilai di dalam array}indeks := 0;for i:= 1 to 100 dobegin

if (kumpulanNilai[i] = nilaiDicari) thenbegin

indeks := i;goto 9999;

end;end;

9999 : {label untuk keluar dari loop for..do}

{Menampilkan hasil pencarian}if (indeks := 0) then

writeln ('Nilai tidak ditemukan')else

writeln ('Nilai ditemukan pada elemen ke ',indeks);end.


Perhatikan bahwa proses pencarian nilai di dalam array dilakukan sebagai berikut:

1. Mula-mula sebuah variabel bernama indeks ditentukan nilainya sama dengan

nol.

2. Kemudian program melakukan loop untuk memeriksa nilai di dalam setiap

elemen array. Jika nilai dalam salah satu elemen sama dengan nilai yang

dimasukkan oleh operator (yang disimpan dalam variabel nilaiDicari) maka

program akan mencatat nomor elemen tempat ditemukannya nilai yang sama

tersebut ke dalam variabel indeks, kemudian program akan keluar dari loop

dan melompat ke label 9999.

Sedangkan proses penampilan hasil pencarian dilakukan sebagai berikut:

1. Program memeriksa nilai indeks.

2. Jika nilai indeks sama dengan nol, berarti proses pencarian yang

sebelumnya dilakukan tidak berhasil menemukan nilai yang dicari dan

program menampilkan pesan 'Nilai tidak ditemukan'. Program berakhir.

3. Jika nilai indeks tidak sama dengan nol, berarti proses pencarian sebelumnya

berhasil menemukan nilai yang dicari dan program menampilkan pesan 'Nilai

ditemukan pada elemen ke X' dengan X adalah nilai dari variabel indeks.

Contoh 2 [RIN01]

Kita diharuskan membuat sebuah fungsi CariNilai dengan ketentuan sebagai berikut:

Output: Indeks elemen array tempat ditemukannya sebuah nilai yang dicari atau jika

nilai tidak berhasil ditemukan, maka output yang dihasilkan adalah 0.

Input:

1. Array dengan elemen 1..100, yang masing-masing elemennya berisi nilai

bertipe integer. Array dikirim ke dalam fungsi dengan cara pass by reference.

2. N sebagai elemen terakhir dalam array yang menjadi batas proses pencarian.

Syarat: Loop yang digunakan harus while..do.

Fungsi tersebut dapat kita implementasikan sebagai berikut:

type TArray : array [1..100] of integer;

function CariNilai(var kumpulanNilai : TArray;N, nilaiDicari : integer) : integer;

var k : integer;begin

k := 1;while (k < N) and (kumpulanNilai[k]<>nilaiDicari) do

k := k + 1;


if (kumpulanNilai[k] = nilaiDicari) thenCariNilai := k

elseCariNilai := 0;

end;

Cara kerja dari fungsi di atas dapat dijelaskan sebagai berikut:

1. Mula-mula fungsi menentukan bahwa nilai variabel k sama dengan 1.

Variabel k adalah variabel sentinel (counter) yang berfungsi untuk memas-

tikan bahwa jumlah loop yang dilakukan tidak lebih besar dari elemen array

yang menjadi batas terakhir pencarian (N).

2. Kemudian loop dilakukan terus selama nilai k lebih kecil dari N dan selama

nilai yang terdapat dalam elemen array ke k (kumpulanNilai[k]) tidak

sama dengan nilai yang dicari (nilaiDicari). Satu-satunya operasi yang

dilakukan dalam loop tersebut adalah menambah k dengan 1.

3. Jika loop sudah berakhir terdapat 2 kemungkinan. Kemungkinan pertama

adalah k sudah sama dengan nomor elemen batas N. Kemungkinan kedua,

nilai dalam elemen ke k sama dengan nilaiDicari. Jika nilai dalam

elemen k sama dengan nilaiDicari, maka fungsi akan mengembalikan

nilai k (CariNilai := k), tetapi jika tidak, maka fungsi akan

mengembalikan 0 (CariNilai:= 0).

Jika data yang terdapat dalam kumpulan nilai sudah berurutan dari yang nilainya

terkecil hingga yang terbesar, maka kita dapat mengubah statement while..do di atas

menjadi:

while (k < N) and (kumpulanNilai[k]<>nilaiDicari) and (nilaiDicari < kumpulanNilai[k]) do

Dengan statement yang baru ini, proses pencarian hanya akan diteruskan jika nilai

yang dicari lebih kecil dari nilai dalam elemen array ke k. Jika nilai yang dicari lebih

besar dari itu, maka dapat disimpulkan bahwa nilai yang dicari tidak terdapat di

dalam kumpulan nilai, karena dalam array yang nilainya berurutan dari kecil ke

besar, nilai-nilai yang terletak dalam elemen sesudah elemen ke k, pasti akan lebih

besar dari nilai yang dicari.

Catatan:

Bahasa pemrograman Pascal mengharuskan parameter yang dikirimkan kepada

sebuah fungsi memiliki tipe yang standar atau tipe yang sudah dideklarasikan


sebelumnya. Karena itu, kita tidak mungkin mengirimkan array dengan jumlah

elemen yang berbeda-beda ke dalam fungsi di atas. Jika kita memiliki kumpulan nilai

yang kurang atau sama dengan seratus, kita bisa memanfaatkan fungsi di atas untuk

mencari nilai tertentu di dalam kumpulan tersebut dengan cara menyimpan kumpulan

nilai tersebut di dalam array yang tipenya TArray dan kemudian menyimpan jumlah

nilai di dalam kumpulan tersebut ke dalam variabel N. Tetapi jika kumpulan nilai yang

kita miliki lebih dari 100 sehingga tipenya berbeda dengan TArray, maka fungsi di

atas menjadi tidak berguna buat kita. Bagaimana mencari sebuah nilai dari

sekumpulan nilai yang belum kita ketahui pasti jumlahnya atau dari sekumpulan nilai

yang bisa bertambah dan berkurang (sekumpulan nilai yang bersifat dinamis)?

Terdapat dua jawaban terhadap pertanyaan ini:

1. Kumpulan nilai yang kita miliki sebelumnya telah tersimpan di dalam disk

sehingga proses pencarian dilakukan dengan memanfaatkan operasi file.

2. Untuk membuat kumpulan nilai yang jumlahnya bisa bertambah atau

berkurang secara dinamis di dalam memori, dibutuhkan struktur data yang

disebut dengan senarai berkait (linked list). Linked list akan kita bahas dalam

kuliah-kuliah mendatang.

Contoh 3

Kita diharuskan membuat sebuah fungsi CariNilai dengan ketentuan sebagai berikut:

Output: Nomor record tempat ditemukannya sebuah nilai yang dicari atau jika nilai

tidak berhasil ditemukan, maka output yang dihasilkan adalah -1.

Input: Sebuah file bertipe integer di dalam disk yang tidak diketahui panjang

recordnya.

Syarat: Variabel file diasosiasikan dengan file fisik di luar fungsi, tetapi file dibuka

dan ditutup di dalam fungsi.

Fungsi tersebut dapat kita implementasikan sebagai berikut:

type TFile = file of integer;

function CariNilai(var fil : TFile; nilaiDicari : integer) : integer;var nilai : integer;

beginreset(fil);repeat

read(fil, nilai);until (eof(fil)) or (nilai = nilaiDicari);if (nilai = nilaiDicari) then


CariNilai := filepos(fil)-1else

CariNilai := -1;close(fil);

end;

Cara kerja fungsi di atas dapat dijelaskan sebagai berikut:

1. Mula-mula fungsi membuka file yang diasosiasikan dengan variabel fil

untuk dibaca dengan perintah reset.

2. Untuk membandingkan nilai yang dicari (variabel nilaiDicari) dengan

data dalam file, terlebih dahulu fungsi ini harus membaca data dari file lalu

menyimpannya dalam variabel nilai. Sementara itu, proses membaca file

dan membandingkan nilai harus terus dilakukan sampai salah satu dari dua

kondisi tercapai, yaitu file mencapai record terakhir (eof) atau nilai yang

dibaca dari file sama dengan nilai yang dicari (nilai = nilaiDicari).

Karena minimal harus dilakukan satu kali pembacaan dari file sebelum

proses pemeriksaan kondisi bisa dilakukan, maka kita harus menggunakan

loop repeat..until.

3. Kemudian fungsi memeriksa penyebab berakhirnya loop repeat..until. Jika

loop berakhir karena nilai yang dicari sama dengan nilai dari file, maka fungsi

akan mengembalikan posisi record tempat ditemukannya nilai yang dimaksud

(CariNilai := filepos(fil)-1). Jika loop berakhir karena file telah

mencapai batas akhir, maka fungsi mengembalikan nilai -1 (CariNilai:=

-1).

Jika kita mempunyai sebuah file bertipe integer dengan nama 'nilai.dat' yang

sudah berisi kumpulan nilai, fungsi di atas dapat dipanggil dengan baris deklarasi

dan statement sebagai berikut:

varf : Tfile;posisi : integer;

beginassign (f,'nilai.dat');posisi := CariNilai(f,199); {199 adalah nilai yang dicari}if (posisi>=0) then

writeln('Nilai ditemukan pada record ke ', posisi);else

writeln('Nilai tidak ditemukan dalam file');end.

Pertanyaan latihan: Jika anda diharuskan membuat fungsi di atas dengan syarat

bahwa loop yang dipakai adalah for..do atau while..do, bagaimana mengimplementa-

sikannya?


Kelemahan dari metode pencarian beruntun adalah bahwa dalam kasus terburuk

(nilai tidak ditemukan), pembandingan nilai dilakukan sebanyak jumlah data dalam

kumpulan nilai. Dengan demikian, proses pencarian akan bertambah lambat secara

linear dengan bertambahnya banyaknya jumlah data. Jadi jika jumlah data dalam

kumpulan nilai meningkat sebanyak 10 kali lipat, maka lamanya pencarian dalam

kasus terburuk juga akan meningkat 10 kali lipat. Bisa disimpulkan bahwa metode

pencarian beruntun akan sangat lambat jika data yang harus diperiksa berjumlah

sangat banyak.

2. Pencarian Biner (Binary Search) atau Pencarian Bagidua.

Jika data yang kita miliki sudah berurutan, kita dapat melakukan proses

pencarian dengan metode binary search. Salah satu bentuk pencarian biner adalah

metode pencarian yang kita pergunakan dalam kehidupan sehari-hari ketika kita

mencari nomor halaman tertentu dari sebuah buku teks. Untuk mencari nomor

halaman tersebut, kita tidak melakukan proses pencarian secara beruntun dari

halaman pertama sampai dengan halaman terakhir, tetapi kita membagi buku

tersebut menjadi 2 bagian (yang mungkin tidak sama besar) dan kemudian

menentukan apakah halaman yang kita cari berada pada paruh pertama atau paruh

kedua atau tepat pada halaman yang kita bagi. Jika halaman belum ditemukan, kita

mengabaikan salah satu paruh buku yang tidak mungkin mengandung halaman yang

kita cari dan mengulangi proses pembagian terhadap salah satu paruh buku yang

lain, dan kembali memeriksa jika yang dicari berada dalam paruh pertama atau

kedua atau justeru tepat pada halaman yang kita bagi. Proses pembagian terus

dilakukan sampai kita menemukan nomor halaman yang dicari.

Algoritma metode pencarian biner untuk menemukan elemen dalam suatu array

terurut yang berisi nilai yang dicari, dapat dirangkum sebagai berikut:

1. Tentukan elemen tengah dari bagian array yang menjadi sasaran pencarian.

2. Bandingkan nilai dalam elemen tengah dari array yang dimaksud dengan nilai

yang dicari.

3. Jika nilai yang dicari sama dengan nilai dalam elemen tengah tersebut, maka

kembalikan nomor elemen yang dimaksud dan hentikan proses pencarian.

4. Jika nilai yang dicari lebih besar dari nilai dalam elemen tengah, maka

tentukan bahwa bagian array yang menjadi sasaran pencarian berikutnya

adalah bagian array yang awalnya adalah elemen tengah ditambah satu dan

diakhiri oleh elemen terakhir dari bagian array yang sebelumnya menjadi

sasaran pencarian.


5. Jika nilai yang dicari lebih kecil dari nilai dalam elemen tengah, maka

tentukan bahwa bagian array yang menjadi sasaran pencarian berikutnya

adalah bagian array yang awalnya adalah elemen pertama dari bagian array

yang sebelumnya menjadi sasaran pencarian dan diakhiri oleh elemen

tengah dikurangi satu.

6. Ulangi langkah 1 sampai bagian array yang menjadi sasaran pencarian

tinggal 1 elemen (sehingga tidak bisa dibagi dua lagi).

Contoh:

Jika terdapat sebuah array yang elemennya berindeks 1 sampai dengan 15.

Masing-masing elemen berturut-turut berisi nilai sebagai berikut:

1, 2, 8, 25, 30, 49, 50, 55, 60, 61, 68, 70, 72, 84, 90.

a. Jelaskan langkah-langkah pencarian nilai 49 dalam array tersebut dengan

metode pencarian biner, sehingga menghasilkan indeks elemen array tempat

ditemukannya nilai tersebut.

b. Jelaskan langkah-langkah pencarian nilai 71 dalam array tersebut dengan

metode pencarian biner, sehingga menghasilkan kesimpulan bahwa nilai

tersebut tidak berhasil ditemukan.

Jawab a.:

Langkah 1:

Nilai yang dicari = 49.

Elemen tengah = (elemen awal + elemen akhir) div 2 = (1 + 15) div 2 = 8

Nilai elemen tengah = nilai elemen [8] = 55 > 49.

Maka pencarian berikutnya dilakukan pada elemen-elemen di sebelah kiri elemen

tengah, yaitu:

a. Dimulai dari elemen awal sebelumnya (awal = 1)

b. Diakhiri pada elemen tengah sebelumnya dikurangi satu (akhir = tengah – 1

= 8 – 1 = 7).

1, 2, 8, 25, 30, 49, 50, 55, 60, 61, 68, 70, 72, 84, 90.

55 > 49

Langkah 2:

Elemen tengah = (elemen awal + elemen akhir) div 2 = (1 + 7) div 2 = 4.

Nilai elemen tengah = nilai elemen [4] = 25 < 49.


Maka pencarian berikutnya dilakukan pada elemen-elemen di sebelah kanan elemen

tengah:

a. Dimulai dari elemen tengah sebelumnya ditambah satu (awal = tengah + 1 =

4 + 1 = 5)

b. Diakhiri pada elemen akhir sebelumnya (akhir = 7).

1, 2, 8, 25, 30, 49, 50, 55, 60, 61, 68, 70, 72, 84, 90.

25 < 49

Langkah 3:


Nilai elemen tengah = nilai elemen [6] = 49.

Maka nilai ditemukan pada elemen [6].

Jawab b.:

Langkah 1:

Nilai yang dicari 71.

Elemen tengah = (elemen awal + elemen akhir) div 2 = (1 + 15) div 2 = 8



tengah, yaitu:


8 + 1 = 9)


1, 2, 8, 25, 30, 49, 50, 55, 60, 61, 68, 70, 72, 84, 90.

55 < 71

Langkah 2:




tengah:


12 + 1 = 13)


1, 2, 8, 25, 30, 49, 50, 55, 60, 61, 68, 70, 72, 84, 90.

70 < 71


Langkah 3:



Maka pencarian berikutnya dilakukan pada elemen-elemen di sebelah kiri elemen

tengah:

a. Dimulai dari elemen awal sebelumnya (awal = 13)

b. Diakhiri pada elemen tengah sebelumnya dikurangi satu (akhir = 14 – 1 =

13).

1, 2, 8, 25, 30, 49, 50, 55, 60, 61, 68, 70, 72, 84, 90.

84 > 71

Langkah 4:



Karena sudah tidak tersisa bagian array yang belum diperiksa, terbukti dari awal =

akhir = 13, maka bisa disimpulkan bahwa nilai 71 tidak bisa ditemukan.

1, 2, 8, 25, 30, 49, 50, 55, 60, 61, 68, 70, 72, 84, 90.

72 ≠ 71

Berikut ini disajikan program yang menggunakan algoritma pencarian biner [DEI03]:

Output:

1. Layar komputer menampilkan pesan agar operator memasukkan nilai yang

dicari.

2. Layar komputer menampilkan bagian array yang menjadi sasaran pencarian

pada setiap iterasi proses pencarian biner.

3. Layar komputer menandai elemen tengah dari bagian array yang menjadi

sasaran pencarian dengan lambang bintang (*).

4. Layar komputer akan menampilkan nomor elemen tempat ditemukannya nilai

yang dicari atau menampilkan pesan bahwa nilai tidak ditemukan.

Input:

1. Array yang elemennya berjumlah 15 dan masing-masing elemennya berisi

bilangan genap dari 0 sampai dengan 28 secara berurutan.

2. Nilai yang dimasukkan oleh operator untuk dicari di dalam array.


program Pencarian_Biner;const

maxArray = 15;type

TArray = array[1..maxArray] of integer;

function toStr (i : integer) : string;var temp : string;begin

str(i, temp);toStr := temp;

end;

procedure tampilkanBagianArray (var seluruhArray : TArray;awal, akhir, tengah : integer);

var sasaran : string;i : integer;

beginsasaran := '';for i := 1 to 15 dobegin

if (i<awal) or (i>akhir) thensasaran := sasaran + ' '

elseif (seluruhArray[i]<10) then

sasaran := sasaran + '0' + toStr(seluruhArray[i])else

sasaran := sasaran + toStr(seluruhArray[i]);if (i = tengah) then

sasaran := sasaran + '* 'else

sasaran := sasaran + ' ';end; {of for}writeln (sasaran);

end;

function cariSecaraBiner (var seluruhArray : TArray;nilaiDicari : integer) : integer;

var awal, akhir, tengah : integer;begin

awal := 1;akhir := maxArray;repeat

tengah := (awal + akhir) div 2;tampilkanBagianArray (seluruhArray, awal, akhir, tengah);if nilaiDicari > seluruhArray[tengah] then

awal := tengah + 1else

if nilaiDicari < seluruhArray[tengah] thenakhir := tengah - 1;

until (awal>akhir) or (seluruhArray[tengah] = nilaiDicari);

if (seluruhArray[tengah] = nilaiDicari) thencariSecaraBiner := tengah

elsecariSecaraBiner := 0;

end;


{bagian utama program}var

i, nilai, noElemen : integer;kumpulanNilai : TArray;

beginfor i:= 1 to 15 do

kumpulanNilai[i] := (i-1)*2;write ('Silakan masukkan nilai yang dicari: ');readln (nilai);writeln ('Bagian array yang menjadi sasaran pencarian:');noElemen := cariSecaraBiner (kumpulanNilai, nilai);if (noElemen <> 0) then

writeln('Nilai ditemukan pada elemen ke ', noElemen)else

writeln('Nilai tidak ditemukan');end.

Berikut ini disajikan beberapa contoh output dari program di atas:

Contoh Output 1

Silakan masukkan nilai yang dicari: 24Bagian array yang menjadi sasaran pencarian:00 02 04 06 08 10 12 14* 16 18 20 22 24 26 28

16 18 20 22* 24 26 28 24 26* 28

24*Nilai ditemukan pada elemen ke 13

Contoh Output 2

Silakan masukkan nilai yang dicari: 10Bagian array yang menjadi sasaran pencarian:00 02 04 06 08 10 12 14* 16 18 20 22 24 26 2800 02 04 06* 08 10 12 08 10* 12Nilai ditemukan pada elemen ke 6

Contoh Output 3

Silakan masukkan nilai yang dicari: 17Bagian array yang menjadi sasaran pencarian:00 02 04 06 08 10 12 14* 16 18 20 22 24 26 28

16 18 20 22* 24 26 28 16 18* 20

16*Nilai tidak ditemukan

Keunggulan metode pencarian biner adalah bahwa kecepatan pencarian hanya

berkurang secara logaritmik dibanding bertambahnya data. Jumlah pembandingan

dalam proses pencarian biner adalah 2log (N), dengan N adalah jumlah data dalam

kumpulan nilai. Misalnya jumlah pembandingan pada proses pencarian biner yang

datanya berjumlah 64 (26) adalah 2log 64 = 2log 26 = 6 kali dan untuk data sebanyak

65536 (216), jumlah pembandingan adalah 16 kali. Dengan demikian, jika jumlah data


meningkat sebanyak lebih dari 1000 kali lipat (dari 64 menjadi 65536), maka jumlah

pembandingan hanya naik sebanyak 16/6 kali atau kurang dari 3 kali lipat. Atau

dengan kata lain, peningkatan jumlah data lebih dari 1000 kali lipat hanya akan

diikuti dengan penurunan kecepatan pencarian sebanyak kurang dari 3 kali lipat.

Karena itu, proses pengurutan (sorting) adalah hal yang sangat penting untuk

dilakukan terhadap sekumpulan data, mengingat bahwa data yang sudah terurut bisa

memanfaatkan keampuhan dari metode binary search.

REFERENSI:

[DEI03] Deitel. 2003. Java: How To Program, 5th ed. Prentince Hall.

[RIN01] Rinaldi Munir & Leoni Lidya. 2001. Algoritma & Pemrograman Dalam

Bahasa Pascal dan C. Bandung: Informatika.


algoritma dan pemrograman 2 modul 51

Documents