Searching
Searching
adalah
metode pencarian informasi dalam suatu aplikasi, dengan
suatu kunci( key ). Pencarian diperlukan untuk mencari informasi khusus
dari table pada saat lokasi yang pasti dari informasi tersebut sebelumnya tidak
diketahui. Pencarian selalu dinyatakan dengan referensi pada adanya sekelompok
data yang tersimpan secara terorganisasi, kelompok data tersebut kita sebut
table
Jenis-jenis Searching :
Pencarian sekuensial (Sequential searching)
· Pencarian Sekuensial (sequential searching) atau
pencarian berurutan sering disebut pencarian linear merupakan metode pencarian
yang paling sederhana. Pencarian beruntun adalah proses membandingkan
setiap elemen larik satu per satu secara beruntun, mulai dari elemen pertama
sampai elemen yang dicari ditemukan atau seluruh elemen sudah diperiksa.
Pencarian beruntun terbadi dua:
1. Pencarian beruntun pada larik tidak terurut;
2. Pencarian beruntun pada larik terurut.
· Algoritma
Pencarian berurutan menggunakan
prinsip sebagai berikut :
1. data yang ada dibandingkan satu per satu secara berurutan dengan
yang dicari sampai data tersebut ditemukan atau tidak ditemukan.
2. Pada dasarnya, pencarian ini hanya melakukan pengulangan dari 1
sampai dengan jumlah data.
3. Pada setiap pengulangan, dibandingkan data ke-i dengan yang
dicari.
4. Apabila sama, berarti data telah ditemukan.
Sebaliknya apabila sampai akhir pengulangan tidak ada data yang sama, berarti
data tidak ada.
Kelemahan pada kasus yang paling
buruk, untuk N elemen data harus dilakukan pencarian sebanyak N kali pula.
Algoritma pencarian berurutan dapat dituliskan sebagai berikut :
(1)
i ← 0
(2)
ketemu ← false
(3)
Selama (tidak ketemu) dan (i <= N) kerjakan baris 4
(4)
Jika (Data[i] = x) maka ketemu ← true, jika tidak i ← i + 1
(5)
Jika (ketemu) maka i adalah indeks dari data yang dicari, jika data tidak
ditemukan
· Contoh
#include <stdio.h>
#include <conio.h>
void main(){
int data[8]
= {8,10,6,-2,11,7,1,100};
int cari;
int flag=0;
printf("masukkan
data yang ingin dicari = ");scanf("%d",&cari);
for(int
i=0;i<8;i++){
if(data[i] == cari) flag=1;
}
if(flag==1)
printf("Data ada!\n");
else
printf("Data tidak ada!\n");
getch();
return 1;
}
Dari program diatas, terlihat bahwa
dilakukan perulangan untuk mengakses semua elemen array data satu persatu
berdasarkan indeksnya.
·
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.
Pencarian
Beruntun dengan Sentinel
Jika pencarian
bertujuan untuk menambahkan elemen baru setelah elemen terakhir larik, maka
terdapat sebuah varian dari metode pencarian beruntun yang mangkus. Nilai x
yang akan dicari sengaja ditambahkan terlebih dahulu. Data yang ditambahkan
setelah elemen terakhir larik ini disebut sentinel.
Perhatikan array data berikut ini:
0
1
2
3
4
5
6 indeks
|
3
|
12
|
9
|
-4
|
21
|
6
|
ffea
ffeb ffec
ffed
ffef
fffa
fffb alamat
ü 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.
· Algoritma
Procedure SeqSearchWithSentinel(input L: LarikInt, input n:
integer, input x: integer, output idx: integer)
DEKLARASI
I: integer
ALGORITMA
L[n+1] ← X {sentinel}
I ← 1
While (L[i] ≠ x) do
I ← i+1
Endwhile
If idx = n+1 then
idx ← -1
else
idx ← 1
endif
· Contoh
#include <stdio.h>
#include <conio.h>
void main(){
int data[7] =
{3,12,9,-4,21,6};
int cari,i;
printf("masukkan data
yang ingin dicari = ");scanf("%d",&cari);
data[6] = cari;
i=0;
while(data[i] != cari)
i++;
if(i<6)
printf("Data ada!\n"); else printf("Data tidak ada!\n");
getch;
return 1;
}
Pencarian Biner (binary
search)
Terdapat metode
pencarian pada data terurut yang paling efficient, yaitu metode pencarian
bagidua atau pencarian biner (binary search). Metode ini
digunakan untuk kebutuhan pencarian dengan waktu yang cepat. Prinsip pencarian
dengan membagi data atas dua bagian mengilhami metode ini. Data yang disimpan
di dalam larik harus sudah terurut.
BST adalah binary
tree yang mana data di dalamnya tersusun sedemikian rupa sehingga pada setiap
subtree di dalamnya berlaku:
setiap data di subtree kiri < data
root subtree < setiap data di subtree kanan.
·
Algoritma
class BinaryNode {
void
printInOrder( )
{
if( left != null )
left.printInOrder(
);
// Left
System.out.println(
element ); //
Node
if( right != null )
right.printInOrder(
);
// Right
}
}
class BinaryTree {
public void printInOrder( )
{
if( root != null )
root.printInOrder( );
}
}
Prinsip dari
pencarian biner dapat dijelaskan sebagai berikut :
1.
mula-mula diambil posisi awal 0 dan
posisi akhir = N - 1, kemudian dicari posisi data tengah dengan rumus (posisi
awal + posisi akhir) / 2.
2.
Kemudian data yang dicari
dibandingkan dengan data tengah.
3.
Jika lebih kecil, proses dilakukan
kembali tetapi posisi akhir dianggap sama dengan posisi tengah –1.
4.
Jika lebih besar, porses dilakukan
kembali tetapi posisi awal dianggap sama dengan posisi tengah + 1.
5.
Demikian seterusnya sampai data
tengah sama dengan yang dicari.
Algoritma pencarian biner dapat dituliskan sebagai berikut
:
1.
L ← 0
2.
R ← N - 1
3.
ketemu ← false
4.
Selama (L <= R) dan (tidak ketemu)
kerjakan baris 5 sampai dengan 8
5.
m ← (L + R) / 2 83
6.
Jika (Data[m] = x) maka ketemu ← true
7.
Jika (x < Data[m]) maka R ← m – 1 Jika (x > Data[m]) maka L ← m + 1
8.
Jika (ketemu) maka m adalah indeks
dari data yang dicari, jika tidak data tidak ditemukan.
·
Contoh
int binary_search(int cari){
int l,r,m;
l =
0;
r = n-1;
int
ktm = 0;
while(l<=r
&& ktm==0){
m = (l+r)/2;
if(data[m] == cari) ktm=1;
else
if (cari < data[m]) r=m-1;
else
l=m+1; {
if(ktm==1)
return 1; else return 0;
}
}
}
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. Jadi kita mencari data secara relatif
terhadap jumlah data. Rumus posisi relatif kunci pencarian dihitung dengan
rumus:
Posisi = kunci –
data[low] x (hight – low) + low
Data[hight] – data[low]
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
|
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.
· Contoh Program
#include <stdio.h>
#include <stdlib.h>
#define MAX 5
int interpolationsearch(int a[],int low,int high,int x){
int mid;
while(low<=high){
mid=low+(high-low)*((x-a[low])/(a[high]-a[low]));
if(x==a[mid])
return
mid+1;
if(x<a[mid])
high=mid-1;
else
low=mid+1;
}
return -1;
}
int main(){
int arr[MAX];
int i,n;
int val,pos;
printf("\nEnter total elements (n
< %d) : ",MAX);
scanf("%d",&n);
printf("Enter %d Elements :
",n);
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
printf("\nLIST :
");
for(i=0;i<n;i++)
printf("%d\t",arr[i]);
printf("\nSearch For
: ");
scanf("%d",&val);
pos=interpolationsearch(&arr[0],0,n,val);
if(pos==-1)
printf("\nElement %d not found\n",val);
else
printf("\nElement %d found at position %d\n",val,pos);
return 0;
}
0 komentar:
Posting Komentar