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. Pada umumnya dikenal dua metode searching antara
lain :
o
Sequential search
o
Binary Search
1.
Sequential search
Sequential search
merupakan langkah membandingkan data yang dicari dengan setiap elemen data
satu-persatu secara beruntun, pencarian dimulai dari elemen pertama hingga
elemen ditemukan atau seluruh elemen sudah dibandingkan.
Contoh Program Sequential Search
#include <stdio.h>
#define max 10
//fungsi memasukkan nilai pada array yang akan dicari
void bacadata(int a[], int n)
{
int i;
printf("masukkan: \n");
for (i=0;i<n;i++)
{
printf("data ke - %d =
",i+1);
scanf(" %d",&a[i]);
}
}
//fungsi untuk mencetak data yang telah dimasukkan nilai
void cetakdata(int a[], int n)
{
int i;
for(i=0;i<n;i++)
{
printf(" %d ",a[i]);
}
printf("\n");
}
//fungsi pencarian terhadap data dengan nilai yang ingin dicari
int seqsearch(int a[],int n,int key)
{
int i = 0;
while ((i<n)&&(a[i]
!=key)) {
i++;
}
if (a[i]==key) return i;
else
return -1;
}
//program utama yang memanggil fungsi atau subprogram
main()
{
int n,a[max], v, p;
printf(" PROGRAM MENCARI SECARA SEQUENSIAL\n");
printf("jumlah data: ");
scanf(" %d",&n);
if (n > max )
{
printf("jumlah data maksimal
%d",max);
return -1;
}
bacadata(a,n);
printf("array data: ");
cetakdata(a,n);
printf("nilai yang dicari: ");
scanf("%d",&v);
p = seqsearch(a,n,v);
if (p>=0) printf("nilai %d ada diposisi ke - %d \n",v,p+1);
else printf("nilai %d tidak ada dalam array \n",v);
}
2.
Binary Search
Salah satu syarat
agar pencarian biner dapat dilakukan adalah data sudah dalam keadaan urut.
Dengan kata lain, apabila data belum dalam keadaan urut, pencarian biner tidak
dapat dilakukan.
Dalam
kehidupan sehari-hari, sebenarnya kita juga sering menggunakan pencarian biner.
Misalnya saat ingin mencari suatu kata dalam kamus Prinsip dari pencarian biner
dapat dijelaskan sebagai berikut : mula-mula diambil posisi awal 0 dan posisi
akhir = N - 1, kemudian dicari posisi data tengah dengan rumus (posisi awal +
posisi akhir) / 2. Kemudian data yang dicari dibandingkan dengan data tengah.
Jika lebih kecil, proses dilakukan kembali tetapi posisi akhir dianggap sama
dengan posisi tengah –1. Jika lebih besar, porses dilakukan kembali tetapi
posisi awal dianggap sama dengan posisi
3
|
9
|
11
|
12
|
15
|
17
|
20
|
23
|
31
|
35
|
Awal
tengah
akhir
Mula-mula dicari data tengah, dengan rumus (0 + 9) / 2 = 4. Berarti
data tengah adalah data ke-4, yaitu 15. Data yang dicari, yaitu 17,
dibandingkan dengan data tengah ini. Karena 17 > 15, berarti proses
dilanjutkan tetapi kali ini posisi awal dianggap sama dengan posisi tengah + 1
atau 5.
3
|
9
|
11
|
12
|
15
|
17
|
20
|
23
|
31
|
35
|
Awal tengah akhir
Data tengah yang baru didapat dengan rumus (5 + 9) / 2 = 7. Berarti
data tengah yang baru adalah data ke-7, yaitu 23. Data yang dicari yaitu 17
dibandingkan dengan data tenah ini. Karena 17 < 23, berarti proses
dilanjukkan tetapi kali ini posisi akhir dianggap sama dengan posisi tengah – 1
atau 6.
3
|
9
|
11
|
12
|
15
|
17
|
20
|
23
|
31
|
35
|
Awal = tengah akhir
Data tengah yang baru didapat dengan rumus (5 + 6) / 2 = 5. Berarti
data tengah yang baru adalah data ke-5, yaitu 17. data yang dicari dibandingkan
dengan data tengah ini dan ternyata sama. Jadi data ditemukan pada indeks ke-5.
Pencarian biner ini akan berakhir jika data ditemukan atau posisi awal lebih
besar daripada posisi akhir. Jika posisi sudah lebih besar daripada posisi
akhir berarti data tidak ditemukan.
Untuk lebih jelasnya perhatikan contoh pencarian data 16 pada data
diatas. Prosesnya hampir sama dengan pencarian data 17. Tetapi setelah posisi
awal 5 dan posisi akhir 6, data tidak ditemukan dan 16 < 17, maka posisi
akhir menjadi posisi tengah – 1 atau = 4 sedangkan posisi awal = 5.
3
|
9
|
11
|
12
|
15
|
17
|
20
|
23
|
31
|
35
|
Awal akhir
Disini dapat dilihat bahwa posisi awal lebih besar daripada posisi
akhir, yang artinya data tidak ditemukan.
Algoritma pencarian
biner dapat dituliskan sebagai berikut :
1. L ← 0
2. R ← N – 1
3. ditemukan ← false
4. Selama (L <= R) dan
(tidak ditemukan) kerjakan baris 5 sampai dengan 8
5. m ← (L + R) / 2
6. Jika (Data[m] = x) maka
ditemukan ← true
7. Jika (x < Data[m])
maka R ← m – 1
8. Jika (x > Data[m])
maka L ← m + 1
9. Jika (ditemukan) maka m
adalah indeks dari data yang dicari, jika tidak data tidak ditemukan.
Contoh Program Binary
Search
#include<stdio.h>
#include<conio.h>
#include<iostream.h>
void main()
{
//deklarasi variabel
int A[10],n, i,j,k,tkr,right,left,middle,tm;
//proses penginputan data
cout<<"Masukkan jumlah data =
";
cin>>n;
for(i=0;i<n;i++)
{
cout<<"Masukkkan
data ke - "<<(i+1)<<" = ";
cin>>A[i];
}
cout<<"Masukkan data yang akan
anda cari :";
cin>>k;
//proses pengurutan data
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if (A[i]>A[j])
{
tkr=A[i];
A[i]=A[j];
A[j]=tkr;
}
}
}
//proses pencarian data
tm=0;
right=n;
left=0;
while(right>=left)
{
middle=(right+left)/2;
if(A[middle]==k)
{
tm++;
}
if(A[middle]<k)
{
left=middle+1;
}
else
{
right=middle-1;
}
}
if (tm>0)
{
cout<<"Data
" << k << " yang dicari ada dalam
array"<<endl;
}
//jika tidak ditemukan
else
{
cout<<"Data
tidak ditemukan dalam array"<<endl;
}
getch();
}
