Pencarian merupakan sebuah algoritma dasar yang sering diperlukan dalam pembuatan program. Berbagai algoritma pencarian telah diciptakan dan dapat digunakan. Pemahaman tentang beberapa algoritma pencarian dasar perlu diketahui, termasuk cara penggunaannya dalam program. 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. 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). Penyisipan data ke dalam kumpulan data (perlu dimulai dengan pencarian apakah data tersebut telah ada sehingga terhindar dari duplikasi data).
SEQUENTIAL SEARCH
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.
Algoritma :
{
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;
}
BINARY SEARCH
Binary search, Pencarian secara biner, digunakan ketika sebuah komputer harus mencari posisi sebuah simbol dalam daftar urut. Komputer akan mencari simbol dari tengah daftar sampai data terakhir, dan membandingkannya dengan simbol yang sedang dicari. Apabila simbol tersebut sudah ditemukan, pencarian pada setengah daftar sisanya akan dihentikan. 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).
Algoritma :
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();
}
ALGORITMA PENCARIAN LAIN
1. Interpolation Search
Interpolation Search adalah sebuah algoritma atau metode untuk mencari nilai key yang diberikan dalam array diindeks yang telah diperintahkan oleh nilai – nilai kunci. Metode ini didasari pada proses pencarian nomor telepon pada buku telepon yang mana manusia mencari melalui dengan nilai kunci yang terdapat pada buku. Teknik searching ini dilakukan dengan perkiraan letak data.
Algoritma :
Anda memiliki rekaman 10,20,30,40,50,60,70,80,90.kita mau mencari nilai 80
Langkah-langkah :
Iterasi I
awal = 1 => merupakan kunci awal
akhir = 9 => merupakan kunci akhir
berikut = 1 + (80 – 10)/(90 – 10) x (9 -1) =(1 merupakan kunci awal, 80 merupakan nilai cari, 10 merupakan nilai awal,90 adalah nilai akhir)
= 1 + (70)/(80) x (8)
= 1 + (0,875) x (8)
= 1 + (7)
= 8
akhir = 9 => merupakan kunci akhir
berikut = 1 + (80 – 10)/(90 – 10) x (9 -1) =(1 merupakan kunci awal, 80 merupakan nilai cari, 10 merupakan nilai awal,90 adalah nilai akhir)
= 1 + (70)/(80) x (8)
= 1 + (0,875) x (8)
= 1 + (7)
= 8
Kc : Kb => 80 = 80
Ketemu pada iterasi pertama
2. Grover Search
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. Kompleksitas algoritma ini adalah O(N).
SHANTY ARIESTANIA_30110393_PIS-10-02
