PIS 10-02_30110333_Algoritma Pencarian

Pencarian berurutan menggunakan prinsip sebagai berikut : data
yang ada dibandingkan satu per satu secara berurutan dengan yang dicari sampai data
tersebut ditemukan atau tidak ditemukan.jika kita ingin mengubah data atau menghapus data langkah pertama adalah mencari data jika data yang kita cari tentu data itu bisa dihapus atau diedit. 

Penggunaan Pencarian :

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

Pada kasus yang paling
buruk, untuk N elemen data harus dilakukan pencarian sebanyak N kali pula.
Algoritma pencarian berurutan dapat dituliskan sebagai berikut :

1 i ← 0
2 ketemu ← false
3 Selama (tidak ketemu) dan (i <= N) kerjakan baris 4
4 Jika (Data[i] = x) maka ketemu ← true, jika tidak i ← i + 1
5 Jika (ketemu) maka i adalah indeks dari data yang dicari, jika tidak data tidak
ditemukan
Di bawah ini merupakan fungsi untuk mencari data menggunakan pencarian
sekuensial.

int SequentialSearch(int x)
{
int i = 0;
bool ketemu = false;
while ((!ketemu) && (i < Max)){
81
if(Data[i] == x)
ketemu = true;
else
i++;
}
if(ketemu)
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();

}

 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.

Pemenuhan Kendala

Ini adalah satu jenis pencarian yang memecahkan permasalahan pemenuhan kendala dimana, bukan dengan melihat sebuah jalur, solusinya adalah sebuah himpunan nilai yang diberikan pada sebuah himpunan peubah. Karena peubah-peubah dapat diproses dengan urutan apa saja, algoritma pencarian pohon biasa adalah tidak efisien. Metode pemecahan permasalahan kendala memuat pencarian kombinatorial dan lacak balik, keduanya mengambil keuntungan dari kebebasan yang diasosiasikan dengan permasalahan kendala. 

Pencarian Interpolasi

Bayangkan perihal mencari sebuah kata dalam sebuah kamus. Diberikan sembarang kata, anda memiliki beberapa ide perihal dimana membuka kamus untuk mendapatkan huruf pertama dari kata. Dari sana, anda akan memiliki ide untuk membuka beberapa halaman lagi untuk mendapatkan kota yang hampir mirip denan kata. Dan seterusnya, ini adalah ide dasar dari pencarian interpolasi.