Pencarian (searching) merupakan tindakan untuk mendapatkan suatu data. Untuk keperluan mencari data, terdapat beragam algoritma pencarian (search algorithm). Yang dimaksud dengan algoritma pencarian adalah “algoritma yang menerima sebuah argumen a dan mencoba untuk menemukan rekaman yang memiliki kunci a”Sebagai contoh , dikehendaki untuk mendapatkan mahasiswa dengan nomor urut 9834567. Hasilnya adalah rekaman yang berisi data mahasiswa tersebut; yang barangkali berisi nama, alamat, tanggal lahir, dan nama program studi.
Sequential Search adalah teknik pencarian data dimana data dicari secara urut dari depan ke belakang atau dari awal sampai akhir. Kelebihan dari proses pencarian secara sequential ini jika data yang dicari terletak didepan, maka data akan ditemukan dengan cepat. Tetapi dibalik kelebihannya ini, teknik ini juga memiliki kekurangan. Pertama, jika data yang dicari terletak dibelakang atau paling akhir, maka akan membutuhkan waktu yang lama dalam proses pencariannya. Kedua, beban komputer akan semakin bertambah jika jumlah data dalam array sangat banyak.
contoh algoritma pencarian sequential
#include <iostream.h>
#include <conio.h>
int cari_linear(int array[],int ukuran, int cari);
void main()
{
const int ukuran=10;
int array[ukuran]={25,36,2,48,0,69,14,22,7,19};
cout<<"Isi dari array: "<<endl;
for(int i=0;i<ukuran;i++)
cout<<" "<<array[i];
int cari;
int tanda=-1;
cout<<"\n\nMasukkan data yang dicari: ";
cin>>cari;
tanda= cari_linear(array,ukuran,cari);
if (tanda!=-1)
cout<<"\n\nData tersebut ditemukan pada posisi: array["<<
tanda<<"],"<<" atau deret ke-"<<(tanda+1);
else
cout<<"\nData tersebut tidak ditemukan ";
getch();
}
int cari_linear(int array[],int ukuran,int cari)
{
int tanda=-1;
for(int i=0;i<ukuran;i++)
{
if(cari==array[i])
{
tanda=i; break;
}
}
return tanda;
}
contoh algoritma pencarian sequential
#include <iostream.h>
#include <conio.h>
int cari_linear(int array[],int ukuran, int cari);
void main()
{
const int ukuran=10;
int array[ukuran]={25,36,2,48,0,69,14,22,7,19};
cout<<"Isi dari array: "<<endl;
for(int i=0;i<ukuran;i++)
cout<<" "<<array[i];
int cari;
int tanda=-1;
cout<<"\n\nMasukkan data yang dicari: ";
cin>>cari;
tanda= cari_linear(array,ukuran,cari);
if (tanda!=-1)
cout<<"\n\nData tersebut ditemukan pada posisi: array["<<
tanda<<"],"<<" atau deret ke-"<<(tanda+1);
else
cout<<"\nData tersebut tidak ditemukan ";
getch();
}
int cari_linear(int array[],int ukuran,int cari)
{
int tanda=-1;
for(int i=0;i<ukuran;i++)
{
if(cari==array[i])
{
tanda=i; break;
}
}
return tanda;
}
ALGORITMA PENCARIAN BINER (BINARY SEARCH)
Pencarian Biner (Binary Search) pada array yang sudah terurut
Pencarian Biner (Binary Search) dilakukan untuk :
♪ memperkecil jumlah operasi pembandingan yang harus dilakukan antara data yang dicari dengan data yang ada di dalam tabel, khususnya untuk jumlah data yang sangat besar ukurannya.
♪ Prinsip dasarnya adalah melakukan proses pembagian ruang pencarian secara berulang-ulang sampai data ditemukan atau sampai ruang pencarian tidak dapat dibagi lagi (berarti ada kemungkinan data tidak ditemukan).
♪ Syarat utama untuk pencarian biner adalah data di dalam tabel harus sudah terurut, misalkan terurut menaik.
ALGORITMA PENCARIAN BINER
Kamus
Const N : integer = 8 { misalkan jumlah elemen array maksimum = 8 }
Type A = array [ 1 ..... N ] of integer
Cari, BatasAtas, BatasBawah, Tengah : Integer
Ketemu : boolean
ALGORITMA
Input (cari) { meminta nilai data yang akan dicari}
BatasAtas ¬ 1 { indeks array dimulai dari 1 }
BatasBawah ¬ N
Ketemu ¬ False
While (BatasAtas < BatasBawah) and (not ketemu) do
Tengah ¬ (BatasAtas + BatasBawah) div 2
If A [Tengah] = cari then
Ketemu ¬ true
Else
If ( A [Tengah] < cari ) then { cari di bagian kanan }
BatasAtas ¬ Tengah + 1
Else
BatasBawah ¬ Tengah – 1 { cari di bagian kiri }
Endif
Endif
EndWhile
If (ketemu) then
Output ( ‘Data berada di index nomor’, Tengah )
Else Output ( ‘Data tidak ditemukan’ )
End if
ALGORITMA PENCARIAN LAINNYA
Pencarian Interpolasi
Melakukan pencarian dengan membagi medan pencarian menjadi dua bagian yang tidak seimbang, namun diestimasi berdasarkan kunci yang dicari
Keuntungan : jauh lebih efektif daripada sequential maupun binary search
Kekurangan : hanya dapat dilakukan pada rekaman-rekaman yang telah terurut berdasarkan kunci yang dicari dan kuncinya harus bertipe data numeric.
Melakukan pencarian dengan membagi medan pencarian menjadi dua bagian yang tidak seimbang, namun diestimasi berdasarkan kunci yang dicari
Keuntungan : jauh lebih efektif daripada sequential maupun binary search
Kekurangan : hanya dapat dilakukan pada rekaman-rekaman yang telah terurut berdasarkan kunci yang dicari dan kuncinya harus bertipe data numeric.
Algoritma Pencarian Interpolasi
Mulai
1ßAwal
Akhir nß
while Awal < (Kunci(Cari) – Kunci(Awal)) / (Kunci(Akhir)ßAkhir Rasio Awal + Rasio * (Akhir – Awal) if Kunci(Cari) =ß– Kunci(Awal)) Berikut Berikut goto 16 else if Kunci(Cari)ßKunci(Berikut) Hasil > Kunci(Berikut)
Berikut + 1ßAwal
Berikut - 1ßelse Akhir
end if
end while
tidak ketemußHasil
Selesai
Mulai
1ßAwal
Akhir nß
while Awal < (Kunci(Cari) – Kunci(Awal)) / (Kunci(Akhir)ßAkhir Rasio Awal + Rasio * (Akhir – Awal) if Kunci(Cari) =ß– Kunci(Awal)) Berikut Berikut goto 16 else if Kunci(Cari)ßKunci(Berikut) Hasil > Kunci(Berikut)
Berikut + 1ßAwal
Berikut - 1ßelse Akhir
end if
end while
tidak ketemußHasil
Selesai
Pencarian List
Algoritma pencarian list mungkin adalah algoritma pencarian paling dasar. Tujuannya adalah mencari sebuah elemen dari sebuah himpunan dengan suatu kunci (kemungkinan memuat informasi yang terkait dengan kunci). Oleh karena hal ini adalah masalah yang lazim dalam ilmu komputer, kompleksitas komputasi algoritma-algoritma tersebuh telah dipelajri dengan baik. Algoritma paling sederhana adalah pencarian linear, yang secara sederhana melihat setiap elemen dari list secara berurutan. Waktu pengerjaan algoritma ini adalah O(n), dimana n adalah banyaknya elemen dalam list, dan dapat digunakan langsung pada list yang belum diproses. Algoritma pencarian list yang lebih canggih adalah pencarian biner; waktu pengerjaannya adalah O(log n). Waktu pengerjaannya jauh lebih baik daripada pencarian linear untuk list yang memiliki data banyak, tetapi sebelum dilakukan pencarian list terlebih dahulu harus terurut (lihat algoritma pengurutan) dan juga harus dapat diakses secara acak (pengaksesan acak).Algoritma Grover adalah sebuah algoritma kuantum yang menawarkan percepatan kuadrat dibandingkan pencarian linear klasik untuk list tak terurut.
Algortima pencarian brute-force atau pencarian naif/uninformed menggunakan metode yang sederhana dan sangat intuitif pada ruang pencarian,
Sedangkan algoritma pencarian informed menggunakan heuristik untuk menerapkan pengetahuan tentang struktur dari ruang pencarian untuk berusaha mengurangi banyaknya waktu yang dipakai dalam pencarian.