SEARCHING
(PENCARIAN)
Dalam kehidupan sehari-hari
sebenarnya kita sering melakukan pencarian data. Pencarian data sering juga
disebut table look up atau storage and retrieval information adalah suatu proses untuk
mengumpulkan sejumlah informasi di dalam pengingat komputer dan kemudian
mencari kembali informasi yang diperlukan secepat mungkin. Algoritma pencarian
(searching algorithm) adalah
algoritma yang menerima sebuah argument kunci dan dengan langkah-langkah
tertentu akan mencari rekaman dengan kunci tersebut. Setelah proses pencarian
dilaksanakan, akan diperoleh salah satu dari dua kemungkinan, yaitu data yang
dicari ditemukan (successful) atau
tidak ditemukan (unsuccessful)
Ada beberapa pencarian yang akan kita uraikan disini:
·
Pencarian Beruntun (Sekuensial
Search)
·
Pencarian Bagi dua ( Binary
Search)
1.
PENCARIAN BERURUTAN
( SEKUENSIAL SEARCH )
Pencarian berurutan sering disebut pencarian linear merupakan
metode pencarian yang paling sederhana. Pencarian berurutan menggunakan prinsip
sebagai berikut : data yang ada dibandingkan satu per satu secara berurutan
dengan yang dicari sampai data tersebut ditemukan atau tidak ditemukan. Pada
dasarnya, pencarian ini hanya melakukan pengulangan dari 1 sampai dengan jumlah
data. Pada setiap pengulangan, dibandingkan data ke-i dengan yang dicari. Apabila
sama, berarti data telah ditemukan. Sebaliknya apabila sampai akhir pengulangan
tidak ada data yang sama, berarti data tidak ada. Pada kasus yang paling buruk,
untuk N elemen data harus dilakukan pencarian sebanyak N kali pula.
Berikut ini adalah contoh
pencarian sekuensial :
Dari data diatas, larik L mempunyai 6 elemen. Pencarian akan
dimulai dari indeks ke-0 yaitu posisi pertama. Misalkan elemen yang dicari: X =
21. Urutan elemen yang dibandingkan :
Misalkan
elemen yang dicari: X = 13. Urutan elemen yang dibandingkan :
indeks array yang dikembalikan
adalah 0.
Contoh program sekuensial search :
#include <iostream>
using namespace std;
int main()
{
int jml;
int i;
int cari;
int arr[50];
int tanda=-1;
cout<< "Masukkan banyaknya bilangan = ";
cin>>jml;
for(i=0;i<jml;i++)
{
cout<< "Masukkan bilangan
ke- "<<i+1<< " : ";
cin>>arr[i];
}
cout<< "isi dari array : " <<endl;
for(i=0;i<jml;i++)
cout<<" "
<<arr[i];
cout<< "\nMasukkan data yang dicari : ";
cin>>cari;
for(i=0;i<jml;i++)
{
if (cari==arr[i])
{
tanda=i;
break;
}
}
if (tanda!=-1)
cout<< "\n\n Data tidak
ditemukan ";
return 0;
}
|
2.
PENCARIAN BINER(BINARY SEARCH)
Pencarian biner adalah proses mencari data dengan membagi
data atas dua bagian secara terus menerus sampai elemen yang dicari sudah
ditemukan, atau indeks kiri lebih besar dari indeks kanan. Algoritma ini lebih
efisien daripada algoritma pencarian sekuensial, tetapi pencarian ini mempunyai
syarat yaitu bahwa kumpulan data yang harus dilakukan pencarian harus sudah
terurut terlebih dahulu. Karena data sudah terurut, algoritma dapat menentukan
apakah nilai data yang dicari berada sebelum atau sesudah elemen larik yang
sedang dibandingkan pada suatu saat. Dengan cara ini, algoritma dapat lebih menghemat
waktu pencarian.
Prinsip dari
pencarian biner dapat dijelaskan sebagai berikut:
a)
Mula-mula diambil posisi awal 0 dan posisi akhir = N -1,
b)
Kemudian dicari posisi data tengah dengan rumus (posisi awal
+ posisi akhir) / 2.
c)
Kemudian data yang dicari dibandingkan dengan data tengah.
d)
Jika lebih kecil, proses dilakukan kembali tetapi posisi
akhir dianggap sama dengan posisi tengah –1.
e)
Jika lebih besar, porses dilakukan kembali tetapi posisi
awal dianggap sama dengan posisi tengah + 1. Demikian seterusnya sampai data
tengah sama dengan yang dicari.
Contoh program binary seacrh :
#include <iostream>
#include <conio.h>
using namespace std;
int main()
{
const int
Ar[10]= {1,2,3,4,5,6,7,8,9,10};//untuk proses ascending
int tar;
int
awal,tengah,akhir;
cout<<
"Masukkan data yang dicari : ";
cin>>tar;
while
(awal<=akhir)
{
tengah=
(awal+akhir)/2;
if
(tar>Ar[tengah])
{
awal=tengah+1;
}
else if (tar
<Ar[tengah])
{
akhir=tengah-1;
}
else
{
awal=akhir+1;
}
}
if
(tar==Ar[tengah])
{
cout<<
"Data ditemukan ke - "<<tengah+1<<endl;
}
else
{
cout<< "Data tidak ditemukan ";
cout<<endl;
}
return 0;
}
|
Sumber :
