Algoritma dan
Pemrograman
SEARCHING
Searching
Pada suatu data seringkali
dibutuhkan pembacaan kembali
informasi (retrieval information)
dengan cara searching.
Searching adalah pencarian data
dengan cara menelusuri data-
data tersebut.
Tempat pencarian data dapat
berupa array dalam memori, bisa
juga pada file pada external
storage.
Sequential Search
Adalah suatu teknik pencarian data dalam
array (1 dimensi ) yang akan menelusuri
semua elemen-elemen array dari awal
sampai akhir, dimana data-data tidak perlu
diurutkan terlebih dahulu.
Kemungkinan terbaik (best case) adalah jika
data yang dicari terletak di indeks array
terdepan (elemen array pertama) sehingga
waktu yang dibutuhkan untuk pencarian
data sangat sebentar (minimal).
Kemungkinan terburuk (worst case) adalah
jika data yang dicari terletak di indeks array
terakhir (elemen array terakhir) sehingga
waktu yang dibutuhkan untuk pencarian
Sequential Search (2)
Misalnyaterdapat array satu dimensi
sebagai berikut:
0 1 2 3 4 5 6 7
indeks
8 10 6 -2 11 7 1 100 value
21da 21db 21dc 21dd 21de 21df 21e0 21e1 alamat
Kemudian program akan meminta data yang
akan dicari, misalnya 6.
Jika ada maka akan ditampilkan tulisan
“ADA”, sedangkan jika tidak ada maka akan
ditampilkan tulisan “TIDAK ADA”.
Detail Program
#include <iostream>
#include <conio.h>
using namespace std;
main ()
{
int data [8] = {8,10,6,-2,11,7,1,100};
int cari;
int flag=0;
cout<<"Masukkan data yang ingin dicari = ";
cin>>cari;
for (int i=0; i<8; i++){
if (data [i] == cari) flag=1;
}
if (flag==1)
cout<<"Data ada!\n";
else
cout<<" Data tidak ada!\n";
}
Pembahasan Program
Program menggunakan sebuah variabel flag
yang berguna untuk menadai ada atau
tidaknya data yang dicari dalam array data.
Hanya bernilai 0 atau 1.
Flag pertama kali diinisialiasasi dengan nilai
0.
Jika ditemukan, maka flag akan diset menjadi
1, jika tidak ada maka flag akan tetap bernilai
0.
Semua elemen array data akan dibandingkan
satu persatu dengan data yang dicari dan
diinputkan oleh user.
/* Program pencarian sekuensial */ ketemu = i;
}
#include <iostream>
else
using namespace std;
i++;
if (!ketemu)
int cari (int data[ ], int n, int k)
{ posisi= -1;
int posisi, i, ketemu; }
if (n <=0) return posisi;
posisi= -1; }
else int main ()
{ {
ketemu=0;
int data [8] = {10,9,6,4,7,5,4,1};
i=1;
while ((i<n-1) && !ketemu) int dicari=4;
if (data[i] == k)
{ cout<<"Posisi "<<dicari<<" ada dalam array
posisi = i; data ke: "<<cari(data,8,dicari)<<"\n";
return 0;
}
7
Sequential Search with Sentinel
Perhatikan array data berikut ini:
0 1 2 3 4 5 6 indeks
3 12 9 -4 21 6 value
Terdapat 6 buah data dalam array (dari indeks 0 s/d
5) dan terdapat 1 indeks array tambahan (indeks ke
6) yang belum berisi data (disebut sentinel)
Array pada indeks ke 6 berguna untuk menjaga agar
indeks data berada pada indeks 0 s/d 5 saja. Bila
pencarian data sudah mencapai array indeks yang ke-
6 maka berarti data TIDAK ADA, sedangkan jika
pencarian tidak mencapai indeks ke-6, maka data
ADA.
Program
#include <iostream>
#include <conio.h>
using namespace std;
main (){
int data [7] = {3, 12, 9, -4, 21, 6};
int cari, i;
cout<<"Masukkan data yang ingin dicari = ";
cin>>cari;
data[6] = cari;
i=0;
while (data[i] != cari)
i++;
if (i<6)
cout<<"Data ada!\n";
else
cout<<"Data tidak ada!\n";
}
Binary Search
Data yang ada harus diurutkan terlebih dahulu berdasarkan suatu
urutan tertentu yang dijadikan kunci pencarian.
Adalah teknik pencarian data dalam dengan cara membagi data menjadi
dua bagian setiap kali terjadi proses pencarian.
Prinsip pencarian biner adalah:
◦ Data diambil dari posisi 1 sampai posisi akhir N
◦ Kemudian cari posisi data tengah dengan rumus: (posisi awal + posisi
akhir) / 2
◦ Kemudian data yang dicari dibandingkan dengan data yang di tengah,
apakah sama atau lebih kecil, atau lebih besar?
◦ Jika lebih besar, maka proses pencarian dicari dengan posisi awal
adalah posisi tengah + 1
◦ Jika lebih kecil, maka proses pencarian dicari dengan posisi akhir
adalah posisi tengah – 1
◦ Jika data sama, berarti ketemu.
Ilustrasi
Contoh Data:
Misalnya data yang dicari 17
0 1 2 3 4 5 6 7 8
3 9 11 12 15 17 23 31 35
A B C
Karena 17 > 15 (data tengah), maka: awal = tengah + 1
0 1 2 3 4 5 6 7 8
3 9 11 12 15 17 23 31 35
A B C
Karena 17 < 23 (data tengah), maka: akhir = tengah – 1
0 1 2 3 4 5 6 7 8
3 9 11 12 15 17 23 31 35
A=B=C
Karena 17 = 17 (data tengah), maka KETEMU!
Kelebihan dan kekurangan Binary Search
Jika data target K langsung di temukan,
maka proses pembagian ruangan berhenti.
Kemudian print out indeks data elemen pada
array.
Jika data target K < A[middle], maka
pencarian dapat dibatasi hanya dengan
melakukan pencarian pada sisi kiri array dari
A[middle]. Seluruh elemen yang berada di
sebelah kanan dapat di abaikan.
Jika data target K > A[middle], maka akan
lebih cepat jika pencarian di batasi hanya
pada bagian sebelah kanan saja.
Jika seluruh data telah di cari namun tidak
ada, maka diberi nilai seperti -1
Interpolation Search
Teknik ini dilakukan pada data yang sudah terurut
berdasarkan kunci tertentu
Teknik searching ini dilakukan dengan perkiraan letak
data.
◦ Contoh ilustrasi: jika kita hendak mencari suatu nama di
dalam buku telepon, misal yang berawalan dengan huruf
T, maka kita tidak akan mencarinya dari awal buku, tapi
kita langsung membukanya pada 2/3 atau ¾ dari tebal
buku.
Rumus posisi
kunci data
relatif kunci pencarian
[low] dihitung dengan
Posisi
rumus: x(high low) low
data[high] data[low]
Jika data[posisi] > data yg dicari, high = pos – 1
Jika data[posisi] < data yg dicari, low = pos + 1
Kasus
Misal terdapat data sebagai berikut:
Kode Judul Buku Pengarang
025 The C++ Programming James Wood
034 Mastering Delphi 6 Marcopolo
041 Professional C# Simon Webe
056 Pure JavaScript v2 Michael Bolton
063 Advanced JSP & Servlet David Dunn
072 Calculus Make it Easy Gunner Christian
088 Visual Basic 2005 Express Antonie
096 Artificial Life : Volume 1 Gloria Virginia
Penyelesaian
Kunci Pencarian ? 088
Low ? 0
High ? 7
Posisi = (088 - 025) / (096 - 025) * (7 - 0) + 0 = [6]
Kunci[6] = kunci pencarian, data ditemukan : Visual Basic
2005
Kunci Pencarian ? 060
Low ? 0
High ? 7
Posisi = (060 – 025) / (096 – 025) * (7 – 0) + 0 = [3]
Kunci[3] < kunci pencarian, maka teruskan
Low = 3 + 1 = 4
High = 7
Ternyata Kunci[4] adalah 063 yang lebih besar daripada
060.
Berarti tidak ada kunci 060.
Pencarian pada String
#include <iostream>
#include <cstring>
using namespace std;
int string_kar (char st [ ], char k)
{
int i, posisi, panjang;
i=0;
posisi = -1;
panjang = strlen(st);
while ((i<panjang-1) && posisi==-1)
{
if (st[i] == k)
posisi=i;
i++;
}
return posisi;
}
int main ( )
{
char kalimat [ ]="Selamat Belajar Algoritma Searching";
char dicari='B';
cout<<"Posisi "<<dicari<<" di dalam string "<<kalimat<<": "<<string_kar(kalimat, dicari)<<"\n";
return 0;
}
16