Skema Pencarian

Konsep Pencarian
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). Kasus lain yang memerlukan algoritma pencarian adalah penyisipan data ke dalam kumpulan data (perlu dimulai dengan pencarian apakah data tersebut telah ada sehingga terhindar dari duplikasi data).

Pencarian Sekuensial
Pencarian sekuensial (sequential search) adalah 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.
Algoritma pencarian sekuensial ini cocok untuk pencarian nilai tertentupada sekumpulan data terurut maupun tidak. Keunggulan algoritma ini adalah dalam mencari sebuah nilai dari sekumpulan kecil  data. Algoritma ini termasuk algoritma yang sederhana dan cepat karena tidak memerlukan proses persiapan data (misalnya: pengurutan).

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.
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). Karena data sudah terurut, algoritma dapat menentukan apakah nilai data yang dicari berada sebelum atau sesudah elemen larik yang sedang dibandingkan pada suatu saat. Dengan cara ini, algoritma dapat lebih menghemat waktu pencarian.
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 Lain
Pencarian sekuensial dan pencarian biner merupakan algoritma pencarian dasar yang termasuk ke dalam kelompok pencarian daftar (list search). Terdapat pula beberapa algoritma lain yang termasuk pula dalam kelompok pencarian daftar, antara lain:
·  pencarian interpolasi (interpolation search): melakukan pencarian lebih baik daripada pencarian          biner pada larik berukuran besar dengan distribusi seimbang, tapi waktu pencariannya buruk
·  pencarian Grover (Grover’s search): melakukan pencarian dalam waktu singkat, yang merupakan        pengembangan dari pencarian linier biasa pada larik dengan elemen tidak berurut

Selain algoritma pencarian dalam kelompok pencarian daftar, terdapat pula beberapa kelompok algoritma lain. Beberapa di antaranya adalah sebagai berikut:

Kelompok Algoritma	Penjelasan dan Contoh Algoritma
Pencarian tanpa informasi (uninformed search)	Algoritma ini mencari data tanpa ada batasan tipe data persoalan.
Pencarian pohon (tree search)	Algoritma ini mencari data dengan bantuan struktur pohon (eksplisit maupun implisit). · breadth-first search (mencari level demi level) · depth-first search (mencari dengan meraih kedalaman pohon terlebih dahulu) · iterative-deepening search · depth-limited search · bidirectional search · uniform-cost search
Pencarian grafik (graph search)	Algoritma ini mencari data dengan algoritma penelurusuran grafik, misalnya · Djikstra’s algorithm · Kruskal’s algorithm · nearest neighbour algorithm · Prim’s algorithm
Pencarian dengan informasi (informed search)	Algoritma ini mencari data dengan fungsi heuristik yang spesifik pada persoalan tertentu. · best-first search · A*
Jenis lain	· Algoritma pencarian string · Algoritma genetik · Algoritma minimax