Pencarian berurutan sering disebut pencarian linear merupakan metode
pencarian yang paling sederhana.
Pencarian berurutan menggunakan prinsip sebagai berikut : data yang ada
dibandingkan satu per satu secara berurutan dengan yang dicari sampai data
tersebut ditemukan atau tidak ditemukan.
Pada dasarnya, pencarian ini hanya melakukan pengulangan dari 1 sampai
dengan jumlah data. Pada setiap
pengulangan, dibandingkan data ke-i dengan yang dicari. Apabila sama, berarti data telah ditemukan. Sebaliknya apabila sampai akhir pengulangan
tidak ada data yang sama, berarti data tidak ada. Pada kasus yang paling buruk, untuk N elemen
data harus dilakukan pencarian sebanyak N kali pula.
 |
| Gambar 1 Flowchart Pencarian Sequential |
>Algoritma Metode Sequential
procedure
pencarian_sequensial(L:larikint; n,x:integer; var idx : integer);
var
i : integer;
i <- -1;
while (i<n) and (L[i]<>x) do
i <- i+1;
if L[i]=x then
idx <- i
else
idx <- -1;
endif
endprocedure
>Pascal Metode Sequential
program
metode_pencarian_sequensial;
const max = 1000;
type larikint = array [1..max] of integer;
var
data : larikint;
bil,jml_data,cari,indeks : integer;
procedure
pencarian_sequensial(L:larikint; n,x:integer; var idx : integer);
var
i : integer;
begin
i :=
-1;
while (i<n) and (L[i]<>x) do
begin
i := i+1;
if L[i]=x then
idx := i
else
idx := -1;
end;
end;
begin
write('Masukkan Jumlah Data : ');
readln(jml_data);
for bil := 1 to jml_data do
begin
write(' Data ke-',bil,' : ');
readln(data[bil]);
end;
WriteLn;
WriteLn;
write('Masukkan nilai yang akan dicari : ');
readln(cari);
pencarian_sequensial(data,jml_data,cari,indeks);
WriteLn;
WriteLn;
if indeks <> -1 then
write(cari,' ditemukan pada indeks
ke-',indeks)
else
write(cari,' tidak ditemukan');
ReadLn;
end.
>Program Metode
Sequential
2.Pencarian
Biner (Binary Search)
Salah satu syarat agar pencarian biner dapat dilakukan adalah data sudah
dalam keadaan urut. Dengan kata lain,
apabila data belum dalam keadaan urut,pencarian biner tidak dapat
dilakukan. Dalam kehidupan sehari-hari,
sebenarnya kita juga sering menggunakan pencarian biner. Misalnya saat ingin mencari suatu kata dalam
kamus Prinsip dari pencarian biner dapat dijelaskan sebagai berikut : mula-mula
diambil posisi awal 0 dan posisi akhir = N - 1, kemudian dicari posisi data
tengah dengan rumus (posisi awal + posisi akhir) / 2. Kemudian data yang dicari dibandingkan dengan
data tengah. Jika lebih kecil, proses
dilakukan kembali tetapi posisi akhir dianggap sama dengan posisi tengah
–1. Jika lebih besar, porses dilakukan
kembali tetapi posisi awal dianggap sama dengan posisi tengah + 1. Demikian seterusnya sampai data tengah sama
dengan yang dicari. Untuk lebih jelasnya perhatikan contoh berikut. Misalnya ingin mencari data 17 pada
sekumpulan data berikut :
3
|
9
|
11
|
12
|
15
|
17
|
20
|
23
|
31
|
35
|
Awal
tengah akhir
Mula-mula dicari data tengah, dengan rumus (0 + 9) / 2 = 4. Berarti data tengah adalah data ke-4, yaitu
15. Data yang dicari, yaitu 17,
dibandingkan dengan data tengah 82 ini.
Karena 17 > 15, berarti proses dilanjutkan tetapi kali ini posisi
awal dianggap sama dengan posisi tengah + 1 atau 5.
3
|
9
|
11
|
12
|
15
|
17
|
20
|
23
|
31
|
35
|
awal tengah
akhir
Data tengah yang baru didapat dengan rumus (5 + 9) / 2 = 7. Berarti data tengah
yang baru adalah data ke-7, yaitu 23.
Data yang dicari yaitu 17 dibandingkan dengan data tenah ini. Karena 17 < 23, berarti proses dilanjukkan
tetapi kali ini posisi akhir dianggap sama dengan posisi tengah – 1 atau
6.
3
|
9
|
11
|
12
|
15
|
17
|
20
|
23
|
31
|
35
|
awal=tengah
akhir
Data tengah yang baru didapat dengan rumus (5 + 6) / 2 = 5. Berarti data tengah
yang baru adalah data ke-5, yaitu 17.
data yang dicari dibandingkan dengan data tengah ini dan ternyata
sama. Jadi data ditemukan pada indeks
ke-5. Pencarian biner ini akan berakhir jika data ditemukan atau posisi awal
lebih besar daripada posisi akhir. Jika
posisi sudah lebih besar daripada posisi akhir berarti data tidak ditemukan.
Untuk lebih jelasnya perhatikan contoh pencarian data 16 pada data diatas. Prosesnya hampir sama dengan pencarian data
17. Tetapi setelah posisi awal 5 dan
posisi akhir 6, data tidak ditemukan dan 16 < 17, maka posisi akhir menjadi
posisi tengah – 1 atau = 4 sedangkan posisi awal = 5.
3
|
9
|
11
|
12
|
15
|
17
|
20
|
23
|
31
|
35
|
akhir awal
Disini dapat dilihat bahwa posisi
awal lebih besar daripada posisi akhir, yang artinya data tidak ditemukan.
 |
Gambar
2 Flowchart Pencarian Biner
|
>Algoritma Metode Pencarian Biner
procedure
pencarian_biner(L:larikint; n,x:integer; var idx : integer);
var
i,j,k : integer;
ketemu : boolean;
i <- 1;
j <- n;
ketemu<-false;
while (not ketemu) and (i<=j) do
k<- (i+j) div 2;
if (L[k]=x) then
ketemu <- true
else
if (L[k]>x) then
i <- k+1
else
j <- k-1;
endif
if ketemu then
idx:=k
else
idx:=-1;
endprocedure
>Pascal Metode Pencarian Biner
program Metode_pencarian_biner;
const max = 100;
type larikint = array [1..max] of integer;
var
data : larikint;
bil,jml_data,cari : integer;
indeks : integer;
procedure
pencarian_biner(L:larikint; n,x:integer; var idx : integer);
var
i,j,k : integer;
ketemu : boolean;
begin
i := 1;
j := n;
ketemu:=false;
while (not ketemu) and (i<=j) do
begin
k:= (i+j) div 2;
if (L[k]=x) then
ketemu := true
else
if (L[k]>x) then
i := k+1
else
j :=k-1;
end;
if ketemu then
idx:=k
else
idx:=-1;
end;
begin
write('Masukkan Jumlah Data : ');
readln(jml_data);
for bil := 1 to jml_data do
begin
write(' Data ke-',bil,' : ');
readln(data[bil]);
end;
WriteLn;
WriteLn;
write('Masukkan nilai yang akan dicari : ');
readln(cari);
pencarian_biner(data,jml_data,cari,indeks);
WriteLn;
WriteLn;
if indeks <> -1 then
write(cari,' ditemukan pada indeks
ke-',indeks)
else
write(cari,' tidak ditemukan');
ReadLn;
end.
>Program
Metode Pencarian Biner
Daftar Pustaka
>http://www.brpreiss.com/books/opus5/index.html
>Penerbit Informatika (Algoritma Dan Pemrograman/Rinaldi Munir/2011)
>https://id.wikibooks.org/wiki/Ayo_Membuat_Program_Pascal/Algoritma_Sorting_Dasar
Selanjutnya - String Matching >
>https://id.wikibooks.org/wiki/Ayo_Membuat_Program_Pascal/Algoritma_Sorting_Dasar
Selanjutnya - String Matching >
0 komentar:
Posting Komentar