PENCARIAN
Pengertian à Pencarian adalah proses menemukan nilai (data) tertentu dari dalam sekumpulan nilai yang bertipe sama (tipe dasar maupun tipe bentukan). Dengan kata lain, algoritma pencarian adalah algoritma yang mengambil input berupa persoalan dan mengembalikan penyelesaian berupa penemuan nilai yang dicari dalam persoalan inputan.
Penggunaan Pencarian à
v Proses pencarian seringkali diperlukan pada saat program perlu mengubah atau menghapus nilai tertentu (sebelum bisa mengubah atau menghapus, perlu mencari dulu apakah nilai tersebut ada dalam kumpulan nilai tersebut).
v Penyisipan data ke dalam kumpulan data (perlu dimulai dengan pencarian apakah data tersebut telah ada sehingga terhindar dari duplikasi data).
Ada 2 jenis pencarian yaitu à
1. Pencarian Sekuensial : Proses membandingkan setiap elemen larik (array) satu persatu dengan nilai yang dicari secara beruntun, mulai dari elemen pertama sampai elemen yang dicari sudah ditemukan, atau sampai seluruh elemen sudah diperiksa .
-Keunggulan :
*Algoritma pencarian sekuensial ini cocok untuk pencarian nilai tertentu pada sekumpulan data terurut maupun tidak.
*Keunggulan algoritma ini adalah dalam mencari sebuah nilai dari sekumpulan kecil data.
*Termasuk algoritma yang sederhana dan cepat karena tidak memerlukan proses persiapan data (misalnya: pengurutan).
1. Pencarian Biner : 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 .
-Keungggulan :
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, baik terurut secara menaik (ascendant) atau menurun (descendant).
-Penggunaan Pencarian Biner :
Pencarian dalam data terurut bermanfaat misalnya pada penyimpanan data dengan beberapa komponen, program dapat mencari sebuah indeks terurut. Setelah menemukan indeks yang dicari, program dapat membaca data lain yang bersesuaian dengan indeks yang ditemukan tersebut.
NB à Algoritma pencarian sequential dapat digunakan untuk data yang acak maupun terurut.
Jika dilihat dari sisi kinerja dan efisiensi : untuk kasus terburuk (data tidak ditemukan), algoritma pencarian sequential akan sebanding dengan jumlah data. Sedangkan algoritma binary 2logN.
ALGORITMA PENCARIAN LAIN :
Pencarian sekuensial dan pencarian biner merupakan algoritma pencarian dasar yang termasuk dalam kelompok pencarian daftar (list search). Terdapat pula beberapa algoritma lain yang termasuk pula dalam kelompok pencarian daftar, antara lain:
1.Pencarian Interpolasi :
Melakuan pencarian lebih baik dari biner pada lirik berukuran besar dengan distribusi seimbang, tapi waktu pencariannya buruk.Algoritma pencarian interpolasi memiliki kerumitan dalam hal perhitungan untuk menentukan posisi rekaman yang akan diperiksa berikutnya dibandingkan dengan pencarian biner tetapi algoritma pencarian interpolasi memiliki kinerja yang baik untuk rekaman-rekaman yang memiliki kunci yang mendekati seragam.
2.Pencarian Grover :
Melakukan pencarian dalam waktu singkat, yang merupakan pengembangan dari pencarian linier biasa pada lirik dengan elemen tidak berurut.
Pada persoalan pencarian dengan exhaustive search, diberikan suatu fungsi f(x),x=0,1...(N-1), dimana f(x)
adalah fungsi yang akan selalu menghasilkan 0 untuk semua x,kecuali satu nilai x yang akan menghasilkan 1. Tujuan dari persoalan ini adalah mencari nilai x sehingga f(x) = 1. Ide dasar dari algoritma pencarian kuantum (algoritma Grover) adalah misalkan ada N buah status yang berkorespondensi dengan N item dalam suatu daftar tak terurut. Peluang untuk setiap status, bahwa status tersebut adalah yang dicari dalam daftar tersebut adalah 1/N. Dengan prinsip mekanika kuantum, dimungkinkan untuk meningkatkan nilai peluang status yang dicari karena pengaruh status yang lain (status yang bukan status yang dicari), sehingga pada akhirnya status yang dicari akan memiliki nilai peluang tertinggi. Prinsip mekanika kuantum juga memungkinkan untuk berada dalam lebih dari satu status, dan melakukan lebih dari satu komputasi dalam waktu yang bersamaan. Pada pencarian dengan probabilitas pada komputer klasik, peluang untuk status yang dicari akan meningkat sebesar 1/N setiap kali iterasi pada kalang for, sehingga dengan iterasi sebanyak N kali, akan ditemukan solusi dengan nilai peluang tertinggi.
CONTOH PENCARIAN SEKUENSIAL
int i = 0;
bool ditemukan = false;
while ((!ditemukan) && (i < Max))
{
if(Data[i] == x)
ditemukan = true;
else
i++;
}
if(ditemukan)
return i;
else
return -1;
}
CONTOH PENCARIAN BINER
Int data[10] = {1,3,4,7,12,25,40,65,78,90}; //variabel global
int binary_search(int cari)
{
int l,r,m;
int n = 10;
l = 0;
r = n-1;
int ketemu = 0;
while(l<=r && ketemu==0)
{ m = (l+r)/2;
if( data[m] == cari )
ketemu = 1;
else if (cari < data[m])
r = m-1;
else l = m+1; }
if(ketemu == 1)
return 1;
else return 0; }
void main()
{ clrscr();
int cari,hasil;
cout<<"masukkan data yang ingin dicari = "; cin>>cari;
hasil = binary_search(cari);
if(hasil == 1)
{
cout<<"Data ada!"<
}
else
if(hasil == 0)
cout<<"Data Tidak ada!"<
getch();
}
