algoritma pencarian (searching algorithm) filedata searching altien jonathan rindengan, s.si, m.kom....

20
DATA SEARCHING Altien Jonathan Rindengan, S.Si, M.Kom

Upload: buidieu

Post on 17-May-2019

215 views

Category:

Documents


0 download

TRANSCRIPT

Page 1: Algoritma pencarian (searching algorithm) fileDATA SEARCHING Altien Jonathan Rindengan, S.Si, M.Kom. Pendahuluan Algoritma Pencarian : Untuk menemukan suatu data (nilai) tertentu dalan

DATA SEARCHING

Altien Jonathan Rindengan, S.Si, M.Kom

Page 2: Algoritma pencarian (searching algorithm) fileDATA SEARCHING Altien Jonathan Rindengan, S.Si, M.Kom. Pendahuluan Algoritma Pencarian : Untuk menemukan suatu data (nilai) tertentu dalan

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)

Page 3: Algoritma pencarian (searching algorithm) fileDATA SEARCHING Altien Jonathan Rindengan, S.Si, M.Kom. Pendahuluan Algoritma Pencarian : Untuk menemukan suatu data (nilai) tertentu dalan

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

Page 4: Algoritma pencarian (searching algorithm) fileDATA SEARCHING Altien Jonathan Rindengan, S.Si, M.Kom. Pendahuluan Algoritma Pencarian : Untuk menemukan suatu data (nilai) tertentu dalan

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

Page 5: Algoritma pencarian (searching algorithm) fileDATA SEARCHING Altien Jonathan Rindengan, S.Si, M.Kom. Pendahuluan Algoritma Pencarian : Untuk menemukan suatu data (nilai) tertentu dalan

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

Page 6: Algoritma pencarian (searching algorithm) fileDATA SEARCHING Altien Jonathan Rindengan, S.Si, M.Kom. Pendahuluan Algoritma Pencarian : Untuk menemukan suatu data (nilai) tertentu dalan

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 ….

Page 7: Algoritma pencarian (searching algorithm) fileDATA SEARCHING Altien Jonathan Rindengan, S.Si, M.Kom. Pendahuluan Algoritma Pencarian : Untuk menemukan suatu data (nilai) tertentu dalan

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.

Page 8: Algoritma pencarian (searching algorithm) fileDATA SEARCHING Altien Jonathan Rindengan, S.Si, M.Kom. Pendahuluan Algoritma Pencarian : Untuk menemukan suatu data (nilai) tertentu dalan

Sequential Search ….

Page 9: Algoritma pencarian (searching algorithm) fileDATA SEARCHING Altien Jonathan Rindengan, S.Si, M.Kom. Pendahuluan Algoritma Pencarian : Untuk menemukan suatu data (nilai) tertentu dalan

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

Page 10: Algoritma pencarian (searching algorithm) fileDATA SEARCHING Altien Jonathan Rindengan, S.Si, M.Kom. Pendahuluan Algoritma Pencarian : Untuk menemukan suatu data (nilai) tertentu dalan

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]

Page 11: Algoritma pencarian (searching algorithm) fileDATA SEARCHING Altien Jonathan Rindengan, S.Si, M.Kom. Pendahuluan Algoritma Pencarian : Untuk menemukan suatu data (nilai) tertentu dalan

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)

Page 12: Algoritma pencarian (searching algorithm) fileDATA SEARCHING Altien Jonathan Rindengan, S.Si, M.Kom. Pendahuluan Algoritma Pencarian : Untuk menemukan suatu data (nilai) tertentu dalan

Binary Search ….

Langkah 3:

Ulangi Langkah 1 hingga x ditemukan atau

i>j (ukuran array sudah 0)

Page 13: Algoritma pencarian (searching algorithm) fileDATA SEARCHING Altien Jonathan Rindengan, S.Si, M.Kom. Pendahuluan Algoritma Pencarian : Untuk menemukan suatu data (nilai) tertentu dalan

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

Page 14: Algoritma pencarian (searching algorithm) fileDATA SEARCHING Altien Jonathan Rindengan, S.Si, M.Kom. Pendahuluan Algoritma Pencarian : Untuk menemukan suatu data (nilai) tertentu dalan

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

Page 15: Algoritma pencarian (searching algorithm) fileDATA SEARCHING Altien Jonathan Rindengan, S.Si, M.Kom. Pendahuluan Algoritma Pencarian : Untuk menemukan suatu data (nilai) tertentu dalan

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

Page 16: Algoritma pencarian (searching algorithm) fileDATA SEARCHING Altien Jonathan Rindengan, S.Si, M.Kom. Pendahuluan Algoritma Pencarian : Untuk menemukan suatu data (nilai) tertentu dalan

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

Page 17: Algoritma pencarian (searching algorithm) fileDATA SEARCHING Altien Jonathan Rindengan, S.Si, M.Kom. Pendahuluan Algoritma Pencarian : Untuk menemukan suatu data (nilai) tertentu dalan

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;

Page 18: Algoritma pencarian (searching algorithm) fileDATA SEARCHING Altien Jonathan Rindengan, S.Si, M.Kom. Pendahuluan Algoritma Pencarian : Untuk menemukan suatu data (nilai) tertentu dalan

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.

Page 19: Algoritma pencarian (searching algorithm) fileDATA SEARCHING Altien Jonathan Rindengan, S.Si, M.Kom. Pendahuluan Algoritma Pencarian : Untuk menemukan suatu data (nilai) tertentu dalan
Page 20: Algoritma pencarian (searching algorithm) fileDATA SEARCHING Altien Jonathan Rindengan, S.Si, M.Kom. Pendahuluan Algoritma Pencarian : Untuk menemukan suatu data (nilai) tertentu dalan