BAB 9BAB 9S e a r c h i n gS e a r c h i n g

SearchingSearching Searching dibutuhkan untuk mencari Searching dibutuhkan untuk mencari

kembali informasi dari data yang kembali informasi dari data yang sudah ada.sudah ada.

Searching adalah pencarian data Searching adalah pencarian data dengan cara menelusuri data-data dengan cara menelusuri data-data tersebut.tersebut.

Data yang dicari dapat berupa array, Data yang dicari dapat berupa array, string atau informasi yang disimpan string atau informasi yang disimpan pada external storage.pada external storage.

Sequencial SearchSequencial Search Adalah teknik pencarian data dalam Adalah teknik pencarian data dalam

array satu dimensi dengan menelusuri array satu dimensi dengan menelusuri semua elemen-elemen array dari awal semua elemen-elemen array dari awal sampai akhir. Data array tidak diurutkan sampai akhir. Data array tidak diurutkan terlebih dahulu.terlebih dahulu.

Waktu tercepat pencarian apabila Waktu tercepat pencarian apabila elemen yang dicari berada pada indeks elemen yang dicari berada pada indeks pertama.pertama.

Waktu terlama pencarian apabila Waktu terlama pencarian apabila elemen berada di akhir rangkaian elemen berada di akhir rangkaian indeks.indeks.

Sequencial Search...Sequencial Search...

Misalnya terdapat array satu dimensi sebagai Misalnya terdapat array satu dimensi sebagai berikut: berikut:

Kemudian program akan meminta data yang akan Kemudian program akan meminta data yang akan dicari, misalnya 6.dicari, misalnya 6.

Jika ada maka akan ditampilkan tulisan “ADA”, Jika ada maka akan ditampilkan tulisan “ADA”, sedangkan jika tidak ada maka akan ditampilkan sedangkan jika tidak ada maka akan ditampilkan tulisan “TIDAK ADA”.tulisan “TIDAK ADA”.

8 10 6 -2 11 7 1 100

1 2 3 4 5 6 7 8

ffea ffeb ffec ffed ffef fffa fffb fffc

indeks

value

alamat

Sequencial Search... Sequencial Search... (Pascal)(Pascal)program cari_data_array;program cari_data_array;

var cari, i, jlh, ada:byte;var cari, i, jlh, ada:byte;var arr:array[1..8] of byte;var arr:array[1..8] of byte;

beginbegin uses crt;uses crt; clrscr;clrscr; arr[1]:=8; arr[2]:=10;arr[1]:=8; arr[2]:=10; arr[3]:=6; arr[4]:=-2;arr[3]:=6; arr[4]:=-2; arr[5]:=11; arr[6]:=7;arr[5]:=11; arr[6]:=7; arr[7]:=1; arr[8]:=100;arr[7]:=1; arr[8]:=100; jlh:=8; ada:=0;jlh:=8; ada:=0; write(‘Cari = ‘);write(‘Cari = ‘); readln(cari);readln(cari);

for i:=1 to jlh dofor i:=1 to jlh do beginbegin if arr[i] = cari thenif arr[i] = cari then ada := 1;ada := 1; break;break; end;end;

if ada = 1 thenif ada = 1 then write(‘Ada’)write(‘Ada’) elseelse write(‘Tidak ada’);write(‘Tidak ada’);end.end.

Sequencial Search with Sequencial Search with SentinelSentinel Perhatikan array data berikut ini: Perhatikan array data berikut ini:

Terdapat 6 buah data dalam array (dari indeks 1 Terdapat 6 buah data dalam array (dari indeks 1 s/d 6) dan terdapat 1 indeks array tambahan s/d 6) dan terdapat 1 indeks array tambahan (indeks ke 7) yang belum berisi data (disebut (indeks ke 7) yang belum berisi data (disebut sentinel)sentinel)

Array pada indeks ke 7 berguna untuk menjaga Array pada indeks ke 7 berguna untuk menjaga agar indeks data berada pada indeks 1 s/d 6 saja. agar indeks data berada pada indeks 1 s/d 6 saja. Bila pencarian data sudah mencapai array indeks Bila pencarian data sudah mencapai array indeks yang ke-7 maka berarti data TIDAK ADA, sedangkan yang ke-7 maka berarti data TIDAK ADA, sedangkan jika pencarian tidak mencapai indeks ke-7, maka jika pencarian tidak mencapai indeks ke-7, maka data ADA.data ADA.

3 12 9 -4 21 6

1 2 3 4 5 6 7

ffea ffeb ffec ffed ffef fffa fffb

indeks

value

alamat

Sequencial Search with Sentinel... Sequencial Search with Sentinel... (Pascal)(Pascal)

program cari_data_array;program cari_data_array;var cari, i, jlh:byte;var cari, i, jlh:byte;var arr:array[1..7] of var arr:array[1..7] of

byte;byte;beginbegin uses crt;uses crt; clrscr;clrscr; arr[1]:=3; arr[2]:=12;arr[1]:=3; arr[2]:=12; arr[3]:=9; arr[4]:=4;arr[3]:=9; arr[4]:=4; arr[5]:=21; arr[6]:=6;arr[5]:=21; arr[6]:=6; jlh:=7; i:=1;jlh:=7; i:=1; write(‘Cari =‘);write(‘Cari =‘); readln(cari);readln(cari);

while arr[i] <> cariwhile arr[i] <> cari i := i+1;i := i+1;

if i = cari thenif i = cari then write(‘Ada’)write(‘Ada’) elseelse write(‘Tidak ada’);write(‘Tidak ada’);end.end.

Binary SearchBinary Search Data yang ada harus diurutkan terlebih dahulu Data yang ada harus diurutkan terlebih dahulu

berdasarkan suatu urutan tertentu yang dijadikan kunci berdasarkan suatu urutan tertentu yang dijadikan kunci pencarian.pencarian.

Adalah teknik pencarian data dengan cara membagi Adalah teknik pencarian data dengan cara membagi data menjadi dua bagian setiap kali terjadi proses data menjadi dua bagian setiap kali terjadi proses pengurutan.pengurutan.

Prinsip pencarian biner adalah:Prinsip pencarian biner adalah: Data diambil dari posisi 1 sampai posisi akhir NData diambil dari posisi 1 sampai posisi akhir N Kemudian cari posisi data tengah dengan rumus Kemudian cari posisi data tengah dengan rumus

(posisi awal + posisi akhir) / 2(posisi awal + posisi akhir) / 2 Kemudian data yang dicari dibandingkan dengan data Kemudian data yang dicari dibandingkan dengan data

yang di tengah, apakah sama atau lebih kecil, atau yang di tengah, apakah sama atau lebih kecil, atau lebih besar.lebih besar.

Jika lebih besar, maka proses pencarian dicari dengan Jika lebih besar, maka proses pencarian dicari dengan posisi awal dengan posisi tengah + 1posisi awal dengan posisi tengah + 1

Jika lebih kecil, maka proses pencarian dicari dengan Jika lebih kecil, maka proses pencarian dicari dengan posisi akhir dengan posisi tengah – 1posisi akhir dengan posisi tengah – 1

Jika data sama, berarti ketemu.Jika data sama, berarti ketemu.

Binary Search...Binary Search...Contoh:Contoh:

Misalnya data yang dicari Misalnya data yang dicari 1717

11 22 33 44 55 66 77 88 9933 99 1111 1212 1515 1717 2323 3131 3535LL MM RRKarena 17 > 15 (data tengah), maka: awal = tengah + 1Karena 17 > 15 (data tengah), maka: awal = tengah + 1

11 22 33 44 55 66 77 88 9933 99 1111 1212 1515 1717 2323 3131 3535

LL MM R RKarena 17 < 23 (data tengah), maka: akhir = tengah – 1Karena 17 < 23 (data tengah), maka: akhir = tengah – 1

11 22 33 44 55 66 77 88 9933 99 1111 1212 1515 1717 2323 3131 3535

L=M=RL=M=RKarena 17 = 17 (data tengah), maka KETEMU!Karena 17 = 17 (data tengah), maka KETEMU!

Binary Search... (Pascal)Binary Search... (Pascal)program cari_data_array;program cari_data_array;var cari,l,r,m,n,ketemu:byte;var cari,l,r,m,n,ketemu:byte;var arr:array[1..9] of byte;var arr:array[1..9] of byte;beginbegin uses crt;uses crt; clrscr;clrscr; arr[1]:=3; arr[2]:=9;arr[1]:=3; arr[2]:=9; arr[3]:=11; arr[4]:=12;arr[3]:=11; arr[4]:=12; arr[5]:=15; arr[6]:=17;arr[5]:=15; arr[6]:=17; arr[7]:=23; arr[8]:=31;arr[7]:=23; arr[8]:=31; arr[9]:=35;arr[9]:=35; n:=9; l:=0, r:=9; ketemu:=0;n:=9; l:=0, r:=9; ketemu:=0; write(‘Cari =‘);write(‘Cari =‘); readln(cari);readln(cari);

while ( l<=r and ketemu=0 )while ( l<=r and ketemu=0 ) beginbegin m := int((l+r)/2)m := int((l+r)/2) if arr[m] = cari thenif arr[m] = cari then ketemu := 1ketemu := 1 elseelse if (cari < arr[m]) thenif (cari < arr[m]) then r := m-1r := m-1 elseelse l := m+1;l := m+1; end;end;

if ketemu = 1if ketemu = 1 write(“Ada”)write(“Ada”) elseelse write(“Tidak ada”);write(“Tidak ada”);end.end.

Interpolasi SearchInterpolasi Search Teknik ini dilakukan pada data yang sudah terurut Teknik ini dilakukan pada data yang sudah terurut

berdasarkan kunci tertentuberdasarkan kunci tertentu Teknik searching ini dilakukan dengan perkiraan Teknik searching ini dilakukan dengan perkiraan

letak data.letak data. Contoh ilustrasi: jika kita hendak mencari suatu nama di Contoh ilustrasi: jika kita hendak mencari suatu nama di

dalam buku telepon, misal yang berawalan dengan huruf dalam buku telepon, misal yang berawalan dengan huruf T, maka kita tidak akan mencarinya dari awal buku, tapi T, maka kita tidak akan mencarinya dari awal buku, tapi kita langsung membukanya pada 2/3 atau 3/4 dari tebal kita langsung membukanya pada 2/3 atau 3/4 dari tebal buku.buku.

Jadi kita mencari data secara relatif terhadap Jadi kita mencari data secara relatif terhadap jumlah data.jumlah data.

Rumus posisi relatif kunci pencarian dihitung Rumus posisi relatif kunci pencarian dihitung dengan rumus:dengan rumus:

lowlowhighxlowdatahighdata

lowdatakunciPosisi

)(][][

][

Interpolasi Search…Interpolasi Search…Kasus: misalkan terdapat data sbb:Kasus: misalkan terdapat data sbb:

KodeKode JudulJudul PengarangPengarang

025025 The C++ ProgrammingThe C++ Programming James WoodJames Wood

034034 Mastering Delphi 6Mastering Delphi 6 MarcopoloMarcopolo

041041 Professional C#Professional C# Simon WebeSimon Webe

056056 Pure JavaScript v2Pure JavaScript v2 Michael BoltonMichael Bolton

063063 Advanced JSP & ServletAdvanced JSP & Servlet David DunnDavid Dunn

072072 Calculus Make it EasyCalculus Make it Easy Gunner ChristianGunner Christian

088088 Visual Basic 2005 ExpressVisual Basic 2005 Express AntonieAntonie

096096 Artificial Life : Volume 1Artificial Life : Volume 1 Gloria VirginiaGloria Virginia

Interpolasi Search… (Pascal)Interpolasi Search… (Pascal)

program cari_data_buku;program cari_data_buku;var cari,l,h,pos:integer;var cari,l,h,pos:integer;beginbegin uses crt;uses crt; clrscr;clrscr; l:=0, h:=8; cari:=088;l:=0, h:=8; cari:=088; pos:=int((088 – 025)/(096 – 025)*(8-0)+0);pos:=int((088 – 025)/(096 – 025)*(8-0)+0); while kode[pos] < cariwhile kode[pos] < cari beginbegin if kode[pos] = cari thenif kode[pos] = cari then write(judul[pos])write(judul[pos]) elseelse l := pos + 1;l := pos + 1; end;end;end.end.

Interpolasi Search… (Penjelasan Interpolasi Search… (Penjelasan Pascal)Pascal)Kasus #1:Kasus #1: Kunci Pencarian? Kunci Pencarian? 088088 Low? Low? 00 High? High? 88 Posisi = Posisi = int((088 - 025) / (096 - 025) * (8 - 0) + 0) = [7]int((088 - 025) / (096 - 025) * (8 - 0) + 0) = [7] Kode[7] = kunci pencarian, data ditemukan: Kode[7] = kunci pencarian, data ditemukan: Visual Basic 2005 Visual Basic 2005

ExpressExpress

Kasus #2:Kasus #2: Kunci Pencarian? Kunci Pencarian? 060060 Low? Low? 00 High? High? 88 Posisi = Posisi = int((060 – 025) / (096 – 025) * (8 – 0) + 0) = [3]int((060 – 025) / (096 – 025) * (8 – 0) + 0) = [3] Kunci[3] < kunci pencarian, maka teruskanKunci[3] < kunci pencarian, maka teruskan Low = Low = 3 + 1 = 43 + 1 = 4 High = High = 88 Posisi = Posisi = int((060 – 025) / (096 – 025) * (8 – 4) + 4) = [5]int((060 – 025) / (096 – 025) * (8 – 4) + 4) = [5] Ternyata Kunci[5] adalah Ternyata Kunci[5] adalah 063063 yang lebih besar daripada yang lebih besar daripada 060060.. Berarti tidak ada kode Berarti tidak ada kode 060.060.