materi Pascal : Search
19 Jun 2013
Definisi Search
Search
adalah suatu proses untuk menemukan informasi dari sejumlah data yang ada .
ada
beberapa metode search, akan tetapi pada bab ini akan dibahas 2 metode yaitu:
1.
Metode
Sequential search
2.
Metode
Binary search
Metode Sequential search
Suatu metode pencarian data dengan
cara membandingkan setiap elemen satu persatu secara beruntun, mulai dari
elemen pertama hingga elemen yang di cari di temukan, atau seluruh elemen sudah di periksa.
Contoh:
13
|
16
|
14
|
21
|
76
|
15
|
1 2
3 4 5 6
Misalkan nilai yang dicari: X= 21
Elemen yang di bandingkan :
13,16,14,21 (ditemukan)
Indeks larik yang dikembalikan IDX=
4
Misalkan nilai yang dicari: X= 13
Elemen yang di bandingkan : 13
(ditemukan)
Indeks larik yang dikembalikan IDX=
1
Setiap elemen pada larik L akan
dibandingkan dengan X mulai dari elemen L[1].
Proses perbandingan akan terus
dilakukan selama indeks larik tidak melebehi N (jumlah larik) dan larik ke [k]
tidak sama dengan X
Dan nilai yang dikembalikan adalah
peubah boolean yaitu Ketemu = true dan tidak ketemu = false.
Procedure
sequentialsearch1(input L : larik, input n: integer, input x:integer, output
ketemu: integer)
{Mencari
keberadaan nilai X di dalam L[1..n].
K.awal: X dan larik L[1..n] sudah
terdefenisih nilainya dan K.Akhir ketemu bernilai True jika x Ditemukan, jika X
tidak di temukan maka ketemu =bernilai False}
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 {di temukan}
Ketemu
ç true
Else
Ketemu
ç false {tidak ada
di dalam larik}
Endif
Metode Binary Search
Suatu
metode pencarian data dengan cara membagi dua data.
Syarat-syarat
yang harus di penuhi pada metode ini adalah:
1. Data harus sudah terurut baik
ascending atau descending.
2. Bagi dua elemen larik pada elemen
tengah
Indeks k=(i+j) div 2
Bagian kiri
L[i..j] dan kanan L[k+1..j]
3. Periksa apakah L[ k] = x ,jika ya
ketemu pencarian selesai.
Jika tidak tanyakan Apakah L[k] < x
jika ya pencarian dilakukan di bagian kiri dan sebaliknya jika L[k] > x di
cari dikanan . hal ini tergantung larik terurut ascending atau descending.
4. Ulangi langkah 1 sampai x di temukan
atau i>j yaitu ukuran larik sudah nol.
Contoh:
Ilustrasi
pencarian data . misalkan Larik L dengan 8 buah elemen terurut menurun sbb:
81
|
76
|
21
|
18
|
16
|
13
|
10
|
7
|
i=1 2 3 4 5 6 7 8=j
misalkan
elemen yang di cari adalah x=18
Langkah
1.
i=
1 dan j=8
indeks
elemen tengah k=(1+8) div 2 = 4(diarsir)
81
|
76
|
21
|
18
|
16
|
13
|
10
|
7
|
1 2 3 4 5 6 7
8
|
|
Kiri Kanan
Langkah
2:
L[4]
=18? Ya ! ( X di temukan, Pencarian selesai)
(ii)
Misalkan elemen yang di cari adalah X=16.
Langkah
1:
i= 1 dan j=8
indeks
elemen tengah k=(1+8) div 2 = 4(diarsir)
81
|
76
|
21
|
18
|
16
|
13
|
10
|
7
|
1
2 3 4 5
6 7 8 |
|
Kiri Kanan
k
Langkah
2:
L[4]
= 16 ? Tidak! Maka akan diputuskan cari di bagian kiri atau bagian kanan.
L[4] > 16 ? Ya! Maka cari dikanan
dengan
i= k+1 =5 dan j =
8(tetap)
16
|
13
|
10
|
7
|
i= 5 6 7 j= 8
 |
Langkah
1:
i=5 dan j= 8
indeks elemen tengah k =(5 + 8) div
2 =6(diarsir)
16
|
13
|
10
|
7
|
i= 5 6 7 j= 8
 |
|
 |
|||
kiri kanan
k
Langkah
2:
L[6]=
16? Tidak
L[6]
>16? Tidak maka cari di bagian kiri
i=5 (tetap) dan
j=k-1 = 5
16
|
i= 5
Langkah
1:
i=5 dan j=5
indeks
elemen tengah k=( 5+5) div 2 = 5( di arsir)
16
|
Langkah
2 L[5] = 16 ? ya! (X di temukan, Pencarian selesai)
Contoh
Program binary search
{* program
mencari data pada suatu larik
* pencarian dilakukan dengan metode binary
search }
PROGRAM
PENCARIAN_BINER;
USES CRT;
TYPE LARIK =
ARRAY[1..100] OF INTEGER;
VAR VEKTOR : LARIK;
KETEMU :
BOOLEAN;
CARI,LOKASI,CACAH, BARIS: INTEGER;
{ ------ PROCEDURE
MEMBACA ELEMEN VEKTOR --------}
PROCEDURE BACA_VEKTOR(VAR VEKTOR: LARIK; VAR N, BARIS :
INTEGER);
VAR I, KOLOM
:INTEGER;
BEGIN
KOLOM :=1;
WRITE('BERAPA CACAH ELEMENNYA: ');
READLN(N);
WRITELN('MASUKKAN
ELEMEN ELEMENNYA(SECARA TERURUT): ');
WRITELN('ASCENDING ATAU DESCENDING');
WRITELN;
FOR I :=1 TO N DO
BEGIN
READLN(VEKTOR[I]);
{ GOTOXY(( I MOD 10) * 6(WHEREY -1)}
writeln(I mod 10)
End;
END;
{------- PROCEDURE UNTUK MENCETAK VEKTOR ------- }
PROCEDURE CETAK_VEKTOR (VEKTOR : LARIK; N: INTEGER);
VAR I : INTEGER;
BEGIN
FOR I := 1 TO N DO
BEGIN
WRITE(VEKTOR[I]:6);
IF I MOD 10 = 0 THEN WRITELN;
END
END;
{------- PROCEDURE
SORT SELEKSI ELEMEN VEKTOR ----}
PROCEDURE SORTIR(VAR VEKTOR: LARIK; N : INTEGER);
VAR
I,J,POSISI,BANTU :INTEGER;
BEGIN
FOR I := 1 TO N-1 DO
BEGIN
POSISI :=I;
FOR J := I+1 TO N DO
IF VEKTOR [POSISI] > VEKTOR[J] THEN POSISI
:= J;
BANTU := VEKTOR[I];
VEKTOR[I]
:=VEKTOR[POSISI];
VEKTOR[POSISI] := BANTU
END
END;
{------ PROSEDUR
UNTUK MENCARI DATA METODE BINARY SEARCH ----}
PROCEDURE MENCARI_BINER (VAR KETEMU : BOOLEAN; VAR LOKASI
: INTEGER;
VAR CARI :
INTEGER;
VEKTOR : LARIK;
N: INTEGER);
VAR ATAS, BAWAH
: INTEGER;
BEGIN
WRITELN;
WRITELN;
WRITE('INPUT
DATA YANG DI CARI: ');READLN(CARI);
ATAS := N;
BAWAH:= 1;
KETEMU:=
FALSE;
WHILE(NOT KETEMU) AND (BAWAH <= ATAS)
DO
BEGIN
LOKASI := (ATAS + BAWAH) DIV 2;
IF CARI = VEKTOR[LOKASI] THEN
KETEMU := TRUE
ELSE IF CARI > VEKTOR[LOKASI] THEN
BAWAH := LOKASI + 1
ELSE
ATAS := LOKASI -1;
END;
END;
{ ---------------
PROGRAM UTAMA --------------------}
BEGIN
CLRSCR;
BARIS := 8;
WRITELN('MENCARI DATA PADA SUATU VEKTOR
DENGAN METODE BINARY SEARCH');
WRITELN('++++++++++++++++++++++++++++++++++++++++++++++++++++++++++');
BACA_VEKTOR(VEKTOR,CACAH,BARIS);
MENCARI_BINER(KETEMU,LOKASI,CARI,VEKTOR,CACAH);
WRITELN; WRITE('VEKTOR DIATAS TELAH
DISORTIR');
WRITELN('
MENJADI (DIBACA PERBARIS): ');
CETAK_VEKTOR(
VEKTOR, CACAH);
WRITELN;
IF KETEMU THEN
BEGIN
WRITELN('BILANGAN"', CARI:1,'" ADA PADA VEKTOR DI ATAS');
WRITE('YAITU PADA ELEMEN KE "
',LOKASI:1);
WRITELN('"DARI VEKTOR TERSORTIR')
END
ELSE
WRITELN(' BILANGAN" ',CARI:1,'"
TIDAK ADA PADA
VEKTOR DIATAS') ;
Readln;
END.
0 komentar: