SEARCHING PADA
C++
Searching,
sesuai dengan namanya searching (mencari) metode ini bertujuan untuk mencari
data dengan cara menelusuri data-data tersebut.
Tempat
data dicari dapat berupa array dalam memori, bisa juga pada file yang ada di
eksternal storage.
Sebagai
contoh :
Jika
diketahui ada sebuah array bernama A yang menampung 10 data yang bertipe
integer yaitu A={1,2,3,4,8,5,7,9,6,0} dan kita diberi tugas untuk mencari
beberapa data misalnya:
·
Jika data yang akan dicari dalam array A adalah
6, maka dengan cepat dapat kita ketahui bahwa data 6 ada dalam array A pada
index ke-8 (index pada array dimulai dari 0).
·
Sedangkan jika data yang akan dicari dalam array
A adalah 10, maka dapat disimpulkan bahwa array A tidak memiliki data 12
tersebut.
Ada 2 macam metode
searching, yaitu :
1)
Sequensial Search; dan
2)
Binary Search
SEQUENSIAL SEARCH
Sequensial search adalah metode
pencarian urut. Metode ini adalah metode pencarian yang paling mudah, karena cara
mencarinya dengan cara menelusuri semua elemen-elemen array dari awal sampai
akhir, dimana data-data tidak perlu
diurutkan terlebih dahulu.
Proses dari
sequensial search adalah :
1) Tentukan banyaknya data yang akan diolah,
misalnya banyak data adalah N.
2) Tentukan data apa yang akan dicari, misalnya
data yang akan dicari adalah C.
3) Deklarasikan sebuah counter untuk menghitung banyak
data yang ditemukan, misalnya counternya adalah K.
4) Inisialisasikan K=0
5) Lakukanlah perulangan sebanyak N kali
(sebanyak data yang akan diolah).
6) Dalam tiap proses perulangan tersebut
periksalah apakah data yang sedang diolah sama dengan data yang dicari.
7) Jika sama K=K+1
8) Jika tidak, lanjutkan proses perulangan.
9) Setelah proses perulangan berhenti,
periksalah nilai K.
10) Jika nilai K>0, artinya data yang dicari
ada dalam array dan tampilkan nilai K ke layer sebagai jumlah data yang
ditemukan.
11) Jika nilai K=0, artinya data yang dicari
tidak ditemukan dalam array dan tampilkan ke layar bahwa data tidak ditemukan
12) Proses selesai.
Dari proses di
atas dapat disimpulkan bahwa dalam mencari data, sequensial search akan
membandingkan satu-persatu data yang ada.
Kita langsung
saja coba studi kasus dan source codenya.
1.
Studi Kasus :
Buatlah program
sequensial search dengan maksimal banyaknya data yaitu 10, dan data yang dicari
yaitu 7 ada 2 buah yang berada di indeks ke-2 dan ke-5.
2.
Carilah data 10 pada array, tetapi data tersebut
tidak ditemukan. Tampilkan di layer bahwa data tidak ditemukan
Source code :
#include<iostream.h>
#include<conio.h>
#include<stdio.h>
void main()
{
int A[10],indeks[10],
i,j,k,n;
cout<<"--------------------------------------------------------------"<<endl;
cout<<"SEQUENSIAL
SEARCH"<<endl;
cout<<"--------------------------------------------------------------"<<endl;
cout<<"INPUTKAN
BANYAKNYA DATA [MAX 10] : ";
cin>>n;
cout<<"--------------------------------------------------------------"<<endl;
for(i=0;i<n;i++)
{
cout<<"INPUTKAN
DATA KE-["<<(i+1)<<"] = ";
cin>>A[i];
}
cout<<"--------------------------------------------------------------"<<endl;
cout<<"DATA YANG
AKAN DICARI : ";
cin>>k;
cout<<"--------------------------------------------------------------"<<endl;
j=0;
for (i=0;i<n;i++)
{
if(A[i]==k)
{
indeks[j]=i;
j++;
}
}
if (j>0)
{
cout<<"DATA
"<<k<<" YANG DICARI ADA "<<j<<"
BUAH"<<endl;
cout<<"DATA
TERDAPAT PADA INDEKS KE : ";
for(i=0;i<j;i++)
{
cout<<indeks[i]<<"
";
}
cout<<endl;
}
else
{
cout<<"DATA TIDAK
DITEMUKAN"<<endl;;
}
cout<<"--------------------------------------------------------------"<<endl;
cout<<"SEQUENSIAL
SEARCH SELESAI !"<<endl;
cout<<"--------------------------------------------------------------"<<endl;
getch();
}
Berikut adalah hasil dari studi kasus di atas
:
1. Hasil studi kasus no. 1 :
2. Hasil studi kasus no.2 :
BINARY
SEARCH
Pada binary search, proses pencarian data
dapat dilakukan jika data sudah terurut.
Prinsip dari binary search, yaitu :
1) Mula-mulanya diambil posisi awal (indeks ke-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.
2) Jika data yang dicari lebih kecil dari data
tengah, proses dilakukan kembali tetapi posisi akhir dianggap sama dengan
posisi tengah –1.
3) Jika data yang dicari lebih besar dari data
tengah, proses dilakukan kembali tetapi posisi awal dianggap sama dengan posisi
tengah +1.
4) Jika data sama,
berarti data ditemukan.
Langsung saja kita ke studi kasus dan source
codenya.
Studi kasus :
1.
Buatlah program binary search dengan metode sorting
apapun (ascending) disini saya menggunakan sorting bubble sort. Kemudian
inputkan banyaknya data (maks. 10), lalu tampilkan data yang diinputkan dan
data yang sudah diurutkan. Kemudian cari data 2. Di sini data 2 tersebut ada
dalam array.
2.
Cari data 10 dalam program binary search. Di sini data 10
tidak ada dalam array, tampilkan pada layer jika data tidak ditemukan.
Source code :
#include<iostream.h>
#include<conio.h>
#include<stdio.h>
void main()
{
int A[10],n, i,j,k,tmp,r,l,m,tm;
cout<<"-------------------------------------------------"<<endl;
cout<<"BINARY
SEARCH"<<endl;
cout<<"-------------------------------------------------"<<endl;
cout<<"INPUTKAN
BANYAKNYA DATA = ";
cin>>n;
cout<<"-------------------------------------------------"<<endl;
for(i=0;i<n;i++)
{
cout<<"INPUTKAN
DATA KE-["<<(i+1)<<"] = ";
cin>>A[i];
}
cout<<"-------------------------------------------------"<<endl;
cout<<"DATA YANG
DIINPUTKAN : "<<endl;
for(i=0;i<n;i++)
{
cout<<A[i]<<"
";
}
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if (A[i]>A[j])
{
tmp=A[i];
A[i]=A[j];
A[j]=tmp;
}
}
}
cout<<endl<<"-------------------------------------------------"<<endl;
cout<<"DATA
SETELAH DIURUTKAN :"<<endl;
for(i=0;i<n;i++)
{
cout<<A[i]<<"
";
}
cout<<endl<<"-------------------------------------------------"<<endl;
cout<<"DATA YANG
DICARI : ";
cin>>k;
cout<<"-------------------------------------------------"<<endl;
tm=0;
r=n;
l=0;
while(r>=l)
{
m=(r+l)/2;
if(A[m]==k)
{
tm++;
}
if(A[m]<k)
{
l=m+1;
}
else
{
r=m-1;
}
}
if (tm>0)
{
cout<<"DATA
"<<k<<" YANG DICARI ADA DALAM ARRAY"<<endl;
}
else
{
cout<<"DATA TIDAK
DITEMUKAN"<<endl;
}
cout<<"-------------------------------------------------"<<endl;
cout<<"BINARY
SEARCH SELESAI !"<<endl;
cout<<"-------------------------------------------------"<<endl;
getch();
}
Berikut adalah hasil dari studi kasus di atas
:
1. Hasil dari studi kasus No.1 :
2. Hasil dari studi kasus No. 2 :
SEKIAN
MATERI SEARCHING DARI SAYA JIKA ADA KEKURANGAN MOHON MAAF
TERIMA
KASIH
Sumber : Materi dari STMIK Mercusuar dan
coding dari Dosen Praktikum Struktur Data : IB Ketut Surya Arnawa, S.Kom.