Searching
Searching adalah suatu proses pencarian data dengan cara menelusuri
data-data tersebut. Tempat pencarian data bisa dari array dalam memori, bisa
juga pada file pada external storage.
Contoh searching :
·
Jika diketahui ada sebuah array / barisan data
bernama A yang menampung 10 data yang bertipe integer sebagai berikut : A={1,9,13,23,7,12}
·
kita diberi tugas untuk mencari beberapa data
misal :
·
Jika data yang akan dicari dalam array A adalah
6, maka dengan cepat dapat kita ketahui bahwa data 7 ada dalam array A pada
index ke-4 (index pada array dimulai dari 0).
·
Sedangkan jika data yang akan dicari dalam array
A adalah, maka dapat disimpulkan bahwa array A tidak memiliki data 2 tersebut.
Pada
umumnya dikenal dua metode searching antara lain :
- Sequensial
search
- Binary
Search
Sequensial sort(pencarian berurutan)
Disebut juga sebagai metode pencarian urut adalah metode
pencarian yang paling mudah. 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.
Sequensial search memiliki 2 kemungkinan. Best case dan
worst case.
·
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 mendekati akhir atau malah yang terakhir
(elemen array terakhir) sehingga waktu yang dibutuhkan untuk pencarian data
sangat lama (maksimal).
Contoh koding sequensial search
|
#include
<iostream>
using
namespace std;
#include
<conio.h>
#include
<iomanip>
int main()
{
int data_c[10] =
{7,9,2,10,15,4,5,6,13,11};
int caridata, i, flag = 0;
cout<<"PENCARIAN DENGAN
SEQUENTIAL SEARCH"<<endl;
cout<<"----------------------------------"<<endl;
cout<<"Data : ";
for(int n=0; n<10; n++)
cout<<setw(4)<<data_c[n];
cout<<endl;
cout<<"\nMasukkan data yang
ingin Anda cari : ";
cin>>caridata;
for(i = 0; i<10; i++)
{
if(data_c[i]==caridata)
{
flag = 1;
break;
}
}
if(flag==1)
{
cout<<"Data ditemukan
pada indek ke-"<<i<<endl;
}
else
{
cout<<"Data tidak
ditemukan"<<endl;
}
getch();
return EXIT_SUCCESS;
}
|
Binary Search
Proses pencarian binary search hanya dapat dilakukan pada
kumpulan data yang sudah diurutkan terlebih dahulu, karena array yang menyimpan
data tersebut akan di bagi 2 dengan 3 variabel yaitu tengah, awal dan akhir.
Algoritma binary search :
- 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, proses dilakukan kembali tetapi posisi awal dianggap sama
dengan posisi tengah +1.
- Jika data sama, berarti data
ditemukan
Keuntungan dari binary search ini adalah dapat pencarian dapat dilakukan
dengan mudah, apalagi jika data yang dihandle jumlah nya banyak.
Sedangkan kelemahannya adalah data harus diurutkan terlebih dahulu sebelum
dilakukan pencarian, sehingga proses yang diperlukan lebih banyak.
Contoh koding C++ binary search
|
#include<iostream>
#include<stdio>
int main ()
{
int n, angka[12], awal, akhir, tengah, temp,
key;
bool ketemu = false;
cout<<"Masukan jumlah data :
";
cin>>n;
for(int i=0; i<n; i++)
{
cout<<"Angka ke -
["<<i<<"] : ";
cin>>angka[i];
}
for (int i=0; i<n; i++)
{
for(int j=0; j< n-i-1; j++)
{
if(angka [j] > angka [j+1])
{
temp=angka[j];
angka[j]=angka[j+1];
angka[j+1]=temp;
}
}
}
cout<<"Data yang telah diurutkan
adalah : ";
for(int i=0; i<n; i++)
{
cout<<angka[i]<<" ";
}
cout<<"\n Masukan angka yang
dicari : ";
cin>>key;
awal=0;
akhir=n-1;
while(awal<=akhir)
{
tengah=(awal + akhir)/2;
if(key == angka[tengah])
{
ketemu=true;
break;
}
else if (key < angka [tengah])
{
akhir = tengah -1;
}
else
{
awal = tengah +1;
}
}
if (ketemu == true)
cout<<"Angka ditemukan!";
else
cout<<"Angka tidak
ditemukan";
return 0;
}
|
Source : Presentasi Matakuliah Struktur Data Stikom Bali
0 komentar:
Posting Komentar