algoritma pencarian (searching algorithm) filedata searching altien jonathan rindengan, s.si, m.kom....
TRANSCRIPT
DATA SEARCHING
Altien Jonathan Rindengan, S.Si, M.Kom
Pendahuluan
Algoritma Pencarian : Untuk menemukan suatu data (nilai) tertentu dalan sekumpulan data yang bertipesama
Tujuannya : dapat melakukan manipulasi terhadapdata tersebut.
Data-data dinyatakan dalam array
Akan diberikan output elemen ke berapa (indeks) data yang kita cari tersebut
Asumsi : Tidak ada duplikasi data (tidak ada data yang sama)
Misalkan ada array sbb:
Akan dicari suatu nilai x dalam array tersebut
Jika x ditemukan, indeks elemen tersebut diisidalam var idx
Jika tidak idx = -1 (misal)
Misalkan x = 46, maka idx = 6
Misalkan x = 30, maka idx = -1
Pendahuluan
21 36 8 7 11 46 68 32 12 18
1 2 3 4 5 6 7 8 9 10
Algoritma Pencarian
Ada 2 algoritma pencarian :
Sequential Search/Linear Search
Binary Search
Sequential Search :
Proses membandingkan setiap elemen array satu
per satu secara beruntun, mulai dari elemen
pertama sampai elemen yang dicari ditemukan
atau seluruh elemen diperiksa
Sequential Search
Nilai yang dicari x = 11
Elemen yang dibandingkan (berturut-turut)
21, 36, 8, 7, 11 (ditemukan)
idx = 5
Nilai yang dicari x = 56
Elemen yang dibandingkan (berturut-turut)
21, 36, 8, 7, 11, 46, 68, 32, 12, 18 (tidak ditemukan)
idx = -1
21 36 8 7 11 46 68 32 12 18
1 2 3 4 5 6 7 8 9 10
Kondisi awal :
data array L[i] sudah diketahui
nilai yang akan dicari (x), sudah diketahui
i:=1;
while (i<n) and (L[i]<>x) do
i:=i+1;
if L[i] = x then
idx:=i
else
idx:=-1;
Sequential Search ….
Sequential Search ….program search_1;
uses crt;
var L:array[1..100] of integer;
i,idx,n,x : integer;
begin
clrscr;
write('Jumlah data : ');readln(n);
for i:=1 to n do
begin
write('Nilai L',i,' : ');readln(L[i]);
end;
write('Nilai yang akan dicari : ');readln(x);
writeln;
i:=1;
while (i<n) and (L[i]<>x) do
i:=i+1;
if L[i] = x then
begin
idx:=i; writeln('Nilai ',x,' ada pada elemen ke-',idx);
end
else
begin
idx:=-1; writeln('Nilai ',x,' tidak ditemukan');
end;
readln;
end.
Sequential Search ….
Binary Search
Binary Search : Proses pencarian dengan membagi
dua kelompok dari data-data yang ada
Asumsi : Data sudah terurut (menurun/menaik)
Diperlukan 2 indeks array yaitu yang terkecil dan
terbesar
Binary Search ….
Langkah-langkah :
Misakan indeks kiri i, dan kanan j. Inisialisasi i=1
dan j= n
Langkah 1:
Bagi 2 elemen array pada elemen tengah. Elemen
tengah adalah elemen dengan indeks k = (i+j)div2
(Elemen tengah L[k], membagi array menjadi 2
bagian yaitu bagian kiri L[i..k-1] dan kanan
L[k+1..j]
Binary Search ….
Langkah 2:
Periksa apakah L[k]=x.
Jika L[k]=x, pencarian selesai.
Jika L[k]≠x, harus ditentukan apakah pencarian
akan dilakukan di array bagian kiri atau kanan.
Jika L[k]<x, maka pencarian pada bagian
kiri/kanan (menurun/menaik)
Jika L[k]>x, maka pencarian pada bagian
kanan/kiri (menurun/menaik)
Binary Search ….
Langkah 3:
Ulangi Langkah 1 hingga x ditemukan atau
i>j (ukuran array sudah 0)
Binary Search ….
Misalkan yang dicari x=18
Langkah 1:
i=1 dan j=8 , k=(1+8)div2=4
Langkah 2 :
Pembandingan : L[4]=18? Ya
(x ditemukan, proses pencarian selesai)
81 76 21 18 16 13 10 7
i=1 2 3 4 5 6 7 8=j
81 76 21 18 16 13 10 7
1 2 3 4 5 6 7 8
Binary Search ….
Misalkan yang dicari x=16
Langkah 1:
i=1 dan j=8 , k=(1+8)div2=4
Langkah 2 :
Pembandingan : L[4]=16? Tidak.
Apakah L[4]>16? Ya, lakukan pencarian di sebelah
kanan dengan i=k+1=4+1=5 dan j=8
81 76 21 18 16 13 10 7
1 2 3 4 5 6 7 8
16 13 10 7
i=5 6 7 8=j
Binary Search ….
Langkah 1’:
i=5 dan j=8 , k=(5+8)div2=6
Langkah 2’ :
Pembandingan : L[6]=16? Tidak.
Apakah L[6]>16? Tidak, lakukan pencarian di sebelah
kiri dengan i=5 dan j=k-1=6-1=5
16
5
16 13 10 7
5 6 7 8
Binary Search ….
Langkah 1’’:
i=5 dan j=5 , k=(5+5)div2=5
Langkah 2’’ :
Pembandingan : L[5]=16? Ya.
(Ditemukan x, proses selesai)
16
5
program search_2;
uses crt;
var
L:array[1..100] of integer;
i,j,k,idx,n,x : integer;
find:boolean;
begin
clrscr;
write('Jumlah data : ');readln(n);
for i:=1 to n do
begin
write('Nilai L',i,' : ');readln(L[i]);
end;
writeln;
write('Nilai yang akan dicari : ');readln(x);
writeln;
i:=1;
j:=n;
find:=false;
while (not find) and (i<=j) do
begin
k:=(i+j) div 2;
if L[k] = x then find:=true
else
if (L[k]>x) then i:=k+1
else
j:=k-1;
end;
if find then
begin
idx:=k;
writeln('Nilai ',x,' ada pada elemen ke-',idx);
end
else
begin
idx:=-1;
writeln('Nilai ',x,' tidak ditemukan');
end;
readln;
end.