ALGORITMA PENCARIAN

Algoritma pencarian (searching algorithma) adalah algoritma yang menerima sebuah argumen kunci dan dengan langkah-langkah tertentu akan mencari rekaman dengan kunci tersebut. Setelah proses pencarian dilaksanakan, akan diperoleh salah satu dari dua kemungkinan, yaitu data yang dicari ditemukan (successful) atau tidak ditemukan (unsuccessful).

Pencarian dapat dilakukan secara internal dan eksternal, yang secara internal meliputi pencarian sekuensial dan pencarian binary.

“Sequential search atau Pencarian sekuensial” bisa disebut dengan pencarian linear yang merupakan model pencarian yang paling simpel dan sederhana banget deh yang dapat dilakukan terhadap suatu kumpulan data. Suatu tekhnik pencarian dalam array (1 dimensi) yang akan menelusuri semua elemen-elemen array dari awal sampai akhir, dimana data-data tidak perlu diurutkan terlebih dahulu. Jadi, Pencarian sekuensial digunakan apabila data dalam keadaan acak atau tidak terurut.

keunggulannya :

•  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).

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;

}

“ Pencarian Binari ( Binary Search)” :

 

“Pencarian Sekuensial” akan memakan banyak waktumu apabila mencari data indeks array yang paling akhir dan ditambah lagi kalau datanya tu banyak banget Apalagi kumpulan data udah dalam keadaan urut, Untuk mengatasi masalah ini dan untuk menyingkat waktu terdapat algoritma yang dirancang agar pencarian data dilakukan secara efesien. Metode yang digunakan dikenal dengan sebutan “pencarian biner atau binary search”. Metode ini merupakan tekhnik pencarian data dalam dengan cara membagi dua bagian setiap kali terjadi proses pengurutan. Data dibagi atas dua bagian secara terus menerus sampai elemen yang dicari sudah ditemukan, atau indeks kiri lebih besar dari indeks kanan.

contoh pencarian binary :

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 :

   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.

Rumus :

awal = 1
akhir = n
Berikut = awal + (Nilai cari – Nilai awal)/(Nilai Akhir – Nilai Awal) x (Akhir – Awal)

Jika Kunci Cari > Kunci Berikut maka Kunci berikut + 1
Jika Kunci Cari < Kunci Berikut Maka Kunci Berikut – 1

Contoh :

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

Kc : Kb => 80 = 80

Ketemu pada iterasi pertama

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.


ISNANI KURNIA PUTRI_30110231_PIS-10-02