sebuah algoritma pencarian dijelaskan secara luas adalah sebuah algoritma yang menerima masukan berupa sebuah masalah dan menghasilkan sebuah solusi untuk masalah tersebut, yang biasanya didapat dari evaluasi beberapa kemungkinan solusi. Sebagian besar algoritma yang dipelajari oleh ilmuwan komputer adalah algoritma pencarian. Himpunan semua kemungkinan solusi dari sebuah masalah disebut ruang pencarian. 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
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.
Pencarian uninformed
Sebuah algoritma pencarian uninformed adalah algoritma yang tidak mempertimbangkan sifat alami dari permasalahan. Oleh karena itu algoritma tersebut dapat diimplementasikan secara umum, sehingga dengan implementasi yang sama dapat digunakan pada lingkup permasalahan yang luas, hal ini berkat abstraksi. Kekurangannya adalah sebagian besar ruang pencarian adalah sangat besar, dan sebuah pencarian uninformed (khususnya untuk pohon) membutuhkan banyak waktu walaupun hanya untuk contoh yang kecil. Sehingga untuk mempercepat proses, kadang-kadang hanya pencarian informed yang dapat melakukannya.
Pencarian Informed
Pada pencarian informed, sebuah heuristik yang khusus untuk permasalahan tertentu digunakan sebagai pedoman. Sebuah heuristik yang baik dapat membuat sebuah pencarian informed bekerja secara dramatis melebihi pencarian uninformed.
Terdapat beberapa algoritma pencarian list informed yang dikenali. Salah satu anggota dari algoritma tersebut adalah sebuah hash tabel dengan sebuah fungsi hashing, yaitu algoritma dengan heuristik yang berdasarkan pada permasalahan yang dihadapi. Sebagian besar algoritma informed adalah mengeksplore pohon. Termasuk di dalamnya adalah pencarian Breadth-first, dan A*. Sebagaimana algoritma uninformed, algoritma informed dapat dikembangkan untuk bekerja pada graf.
Pencarian Adversarial
Dalam permainan seperti catur, terdapat sebuah pohon permainan dari semua kemungkinan gerak dari kedua pemain dan konfigurasi hasil dari papan catur, dan kita dapat mencari pada pohon tersebut untuk menemukan strategi permainan yang efektif. Tipe permasalahan ini memiliki karakteristik unik yang mengharuskan kita memperhatikan semua kemungkinan gerak dari lawan yang mungkin terjadi. Untuk melakukannya, program permainan komputer, atau bentuk lain dari kecerdasan buatan seperti perencanaan mesin, biasanya menggunakan algoritma pencarian seperti algoritma minimaks, pemangkasan pohon pencarian dan pemangkasan alpha-beta.
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.
Pencarian Biner
Pencarian Biner (Bah.Ingg: Binary Search) adalah pencarian data secara eliminasi biner berulang/terus-menerus. Maksudnya adalah pada saat pencarian data, 1 kelompok data yang sudah urut dibagi menjadi 2 subkelompok. Lalu salah satu subkelompok dieliminasi, sehingga ruang lingkup pencarian data menjadi lebih sedikit. Kemudian subkelompok yang tersisa dibagi lagi menjadi 2 subkelompok lagi, demikian dilakukan secara berulang-ulang.
type
TArrString = array of string;
function CariBiner(var Arr: TArrString; Cari: string): LongInt;
var
Awal, Akhir, Tengah, Ketemu: LongInt;
begin
Awal:= Low(Arr);
Akhir:= High(Arr);
Ketemu:= -1;
while (Awal <= Akhir) and (Ketemu = -1) do begin
Tengah:= (Awal + Akhir) shr 1;
if Arr[Tengah] = Cari then Ketemu:= Tengah else begin
if Cari < Arr[Tengah] then Akhir:= Tengah-1 else Awal:= Tengah+1;
end;
end;
CariBiner:= Ketemu;
end;
Penjelasannya:
type
TArrString = array of string;
function CariBiner(var Arr: TArrString; Cari: string): LongInt;
var
Awal, Akhir, Tengah, Ketemu: LongInt;
begin
Awal:= Low(Arr); // Posisi awal pencarian
Akhir:= High(Arr); // Posisi akhir pencarian
Ketemu:= -1; // Asumsi awal: belum ketemu
// Ulangi selama ruang lingkup pencarian masih ada (Awal <= Akhir)
// dan data yang dicari belum ketemu (Ketemu = -1)
while (Awal <= Akhir) and (Ketemu = -1) do begin
// Hitung lokasi data yang di tengah ruang lingkup pencarian
Tengah:= (Awal + Akhir) shr 1;
{ Cek apakah data yang di tengah merupakan data yang dicari,
apabila bukan, pindahkan ruang lingkup pencarian,
kalau data ada di sebelah kiri (lebih kecil <),
maka batas akhir yang dikurangi (Akhir:= Tengah - 1),
sedangkan jika data ada di sebelah kanan,
maka batas awal yang ditambah (Awal:= Tengah + 1) }
if Arr[Tengah] = Cari then Ketemu:= Tengah else begin
if Cari < Arr[Tengah] then Akhir:= Tengah-1 else Awal:= Tengah+1;
end;
end;
CariBiner:= Ketemu;
end
sumber http://id.wikibooks.org/wiki/Ayo_Membuat_Program_Pascal/Algoritma_Pencarian
