Ada beberapa jenis algoritma pencarian yang umum digunakan di antaranya:

1. Linear Search

   Algoritma ini sangat sederhana dan mudah dipahami. Algoritma linear search bekerja dengan cara membandingkan setiap elemen pada list atau array secara berurutan hingga data yang dicari ditemukan atau seluruh elemen sudah dibandingkan.

   Algoritma ini cocok digunakan untuk data yang jumlahnya tidak terlalu besar. Namun, jika data yang dicari berada di posisi akhir atau tidak terdapat dalam list atau array, algoritma ini akan membutuhkan waktu yang lama untuk menyelesaikan pencarian.

2. Binary Search

   Algoritma binary search digunakan untuk mencari data pada list atau array yang sudah terurut. Algoritma ini bekerja dengan membandingkan nilai data yang dicari dengan nilai tengah list atau array. Jika nilai data yang dicari lebih besar dari nilai tengah, maka algoritma akan mencari pada setengah kanan list atau array, dan begitu juga sebaliknya. Binary search memiliki kompleksitas waktu yang lebih baik dibandingkan dengan linear search, namun hanya dapat digunakan pada data yang sudah teruru

   Cara Kerja Binary Search

   • Pertama, pastikan himpunan data terurut secara teratur. Binary search hanya efektif jika himpunan data sudah diurutkan.
   • Tentukan batas awal dan batas akhir dari himpunan data. Batas awal biasanya diatur sebagai indeks pertama (0) dan batas akhir sebagai indeks terakhir (n-1), dengan n adalah jumlah elemen dalam himpunan data.
   • Hitung elemen tengah himpunan data. Ini dilakukan dengan mengambil rata-rata batas awal dan batas akhir, yaitu (batas awal + batas akhir) / 2.
   • Bandingkan elemen tengah dengan elemen yang dicari. Jika elemen tengah sama dengan elemen yang dicari, pencarian selesai dan elemen ditemukan.
   • Jika elemen tengah lebih besar dari elemen yang dicari, maka pindahkan batas akhir menjadi satu posisi sebelum elemen tengah. Ini berarti kita akan mencari di bagian sebelumnya dari himpunan data.
   • Jika elemen tengah lebih kecil dari elemen yang dicari, maka pindahkan batas awal menjadi satu posisi setelah elemen tengah. Ini berarti kita akan mencari di bagian setelahnya dari himpunan data.
   • Ulangi langkah-langkah 3 hingga 6 dengan memperbarui batas awal dan batas akhir. Proses ini berlanjut sampai elemen yang dicari ditemukan atau tidak ada lagi elemen yang perlu diperiksa.
   • Jika elemen yang dicari tidak ditemukan setelah seluruh himpunan data diperiksa, berarti elemen tersebut tidak ada dalam himpunan data.
   • Binary search bekerja dengan membagi himpunan data menjadi dua bagian pada setiap langkahnya. Hal ini mengurangi jumlah elemen yang perlu diperiksa secara eksponensial, sehingga mencapai efisiensi yang tinggi. Kompleksitas waktu dari binary search adalah O(log n), di mana n adalah jumlah elemen dalam himpunan data.
3. Interpolation Search

   Algoritma interpolation search digunakan pada list atau array yang memiliki data terurut dan merata. Algoritma ini bekerja dengan menggunakan estimasi posisi data yang dicari berdasarkan data terkecil dan terbesar pada list atau array.

   Algoritma ini akan mencari data pada posisi yang diperkirakan secara proporsional terhadap data terbesar dan terkecil. Interpolation search dapat lebih cepat daripada binary search jika data yang dicari terdistribusi secara merata, namun jika data tidak merata, algoritma ini mungkin tidak lebih baik dari binary search.

   pada binary search interpolation ini mencari data dengan menggunakan Formula, yaitu sebagai berikut:

   

   pos = low + ((cari - data[low]) * (high - low) /

   (data[high] - data[low]))

   Keterangan Variabel:

   • pos : variabel yang digunakan untuk menampung indeks atau posisi dimana program akan mencari data
   • key : variabel yang berisi data atau nilai yang dicari
   • data : array yang menyimpan banyak nilai dengan tipe yang sama sekaligus
   • low : variabel yang menampung indeks paling awal pada array (indeks 0)
   • high : variabel yang menampung indeks terakhir dari array (indeks n-1)
   • data[low] : nilai pada indeks low
   • data[high] : nilai pada indeks high

   Ilustrasi Agloritma Interpolation Search

   Pada ilustrasi digambarkan sebuah array yang menampung 10 elemen secara terurut. Kita akan mencoba mencari nilai 19 pada array dengan menggunakan pencarian interpolasi

   

   Selanjutnya kita akan mendefinisikan beberapa variabel dengan nilainya yang kita dapat dari ilustrasi sebelumnya. Lalu kita masukkan setiap nilai tersebut ke formula pencarian interpolasi. Maka didapatlah hasil 5,27 dan kita bulatkan menjadi 5.

   

   Setelah mendapatkan indeks pos, maka kemudian kita gunakan untuk mencari dimana angka 19 berada. Seperti yang dapat dilihat pada Pseudo Code, maka kita akan mengecek menggunakan pernyataan if else apakah nilai yang dicari > nilai pada indeks pos. Kita cek apakah 19 > 15 ? ternyata benar maka nilai pos + 1 menjadi 6. Kemudian terjadi perulangan dan terdapat pengecekan kondisi while. Setelah dicek lagi ternyata nilai yang dicari yaitu 19 sama dengan nilai pada indeks ke-6, maka nilai yang dicari telah ditemukan dan proses pencarian pun selesai.

   
4. Hash Search

   Algoritma hash search digunakan pada struktur data hash table. Algoritma ini bekerja dengan memetakan data ke dalam index pada hash table. Setelah data dimasukkan ke dalam hash table, pencarian data hanya membutuhkan waktu konstan, yaitu O(1). Algoritma ini sangat cepat dan efisien, namun memerlukan proses pembuatan hash table yang memakan waktu dan memerlukan alokasi memori yang cukup besar.

5. Exponential Search

   Algoritma exponential search digunakan pada list atau array yang tidak terurut, namun harus memiliki ukuran yang cukup besar. Algoritma ini bekerja dengan mencari range atau jangkauan tempat data yang dicari berada, kemudian melakukan binary search pada jangkauan tersebut. Algoritma ini memanfaatkan fakta bahwa jika data yang dicari berada pada jangkauan yang cukup besar, maka binary search akan lebih cepat daripada linear search.

6. Jump Search

   Algoritma jump search mirip dengan algoritma exponential search, namun menggunakan teknik “jump” untuk mencari jangkauan yang memungkinkan data yang dicari berada di dalamnya.

   Algoritma ini bekerja dengan membagi list atau array menjadi beberapa blok atau segmen, kemudian melakukan “jump” atau melompat dari segmen ke segmen untuk mencari jangkauan yang memungkinkan data yang dicari berada di dalamnya. Setelah ditemukan jangkauan tersebut, dilakukan linear search pada jangkauan tersebut.

7. Ternary Search

   Algoritma ternary search digunakan pada list atau array yang sudah terurut dan memiliki data yang merata. Algoritma ini bekerja dengan membagi list atau array menjadi tiga bagian, kemudian mencari pada bagian mana data yang dicari berada. Algoritma ini menggunakan teknik rekursif dan memerlukan tiga panggilan rekursif untuk menyelesaikan pencarian. Algoritma ini sangat efisien untuk mencari data pada list atau array yang memiliki data terurut dan merata.

   Dalam memilih jenis algoritma pencarian, sangat penting untuk mempertimbangkan kompleksitas waktu dan ruang, serta karakteristik dari data yang akan dicari. Setiap jenis algoritma memiliki kelebihan dan kekurangan masing-masing, sehingga pilihan tergantung pada kebutuhan aplikasi yang digunakan.

8. Sequential Search

   Algoritma pencarian Sekuensial adalah salah satu algoritma pencarian data yang biasa digunakan untuk data yang berpola acak atau belum terurut. Algoritma ini akan mencari data sesuai kata kunci yang diberikan mulai dari elemen awal pada array hingga elemen akhir array. Kemungkinan terbaik (best case) ketika menggunakan algoritma ini adalah jika data yang dicari terletak di indeks awal array sehingga hanya membutuhkan sedikit waktu pencarian. Sedangkan kemungkinan terburuknya (worst case) adalah jika data yang dicari ternyata terletak dibagian akhir dari array sehingga pencarian data akan memakan waktu yang lama.

   Konsep Pencarian Sekuensial:
   • Membandingkan setiap elemen pada array satu per satu secara berurut
   • Proses pencarian dimulai dari indeks pertama hingga indeks terakhir
   • Proses pencarian akan berhenti apabila data ditemukan. Jika hingga akhir array data masih juga tidak ditemukan, maka proses pencarian tetap akan dihentikan
   • Proses perulangan pada pencarian akan terjadi sebanyak jumlah N elemen pada array
   Ilustrasi Sequential Search

   Ilustrasi di atas menunjukkan bagaimana proses dari algoritma pencarian Sekuensial. Algoritma ini mencari angka 2 dengan mengecek setiap elemen pada array. Ketika sudah ditemukan maka proses pencarian dapat diakhiri.

   

   Ilustrasi kedua mirip dengan sebelumnya, perbedaannya yaitu ilustrasi di atas menghitung berapa banyak angka yang dicari muncul pada data, sedangkan ilustrasi sebelumnya akan menghentikan pencarian ketika data yang dicari berhasil ditemukan.

   Pemilihan algoritma ini dapat disesuaikan dengan kebutuhan program kita. Jika kita butuh untuk menghitung berapa banyak angka tersebut muncul pada suatu data, maka kita dapat menggunakan yang seperti ilustrasi kedua.

Berikut ini adalah beberapa karakteristik dari algoritma pencarian:

1. Efisiensi

   Algoritma pencarian harus memiliki kecepatan eksekusi yang efisien dalam mencari data pada list atau array yang besar. Algoritma yang efisien dapat menyelesaikan pencarian dalam waktu yang singkat, sehingga memungkinkan program atau sistem untuk bekerja lebih cepat dan efisien.

2. Akurasi

   Algoritma pencarian harus akurat dan dapat menemukan data yang dicari dengan tepat. Algoritma yang akurat akan menghasilkan data yang sesuai dengan kriteria pencarian, sehingga dapat dipercaya dan diandalkan.

3. Keamanan

   Algoritma pencarian harus aman dan tidak merusak data yang sedang dicari. Algoritma yang aman tidak akan memodifikasi atau merusak data yang sedang dicari, sehingga data tersebut tetap dapat digunakan dan diakses dengan aman.

4. Modularitas

   Algoritma pencarian harus mudah dimodifikasi dan diintegrasikan dengan program atau sistem yang lebih besar. Algoritma yang modular dapat dimodifikasi dengan mudah untuk memenuhi kebutuhan tertentu, dan dapat diintegrasikan dengan program atau sistem yang lebih besar tanpa memerlukan perubahan yang signifikan.

5. Scalability

   Algoritma pencarian harus dapat menangani jumlah data yang semakin besar dengan baik. Algoritma yang scalable dapat menangani jumlah data yang semakin besar dengan baik tanpa mengalami penurunan performa atau kinerja.

6. Keterbacaan

   Algoritma pencarian harus mudah dibaca dan dimengerti oleh programmer lain. Algoritma yang mudah dibaca dan dimengerti akan memudahkan programmer lain untuk memahami dan menggunakan algoritma tersebut, sehingga memungkinkan kolaborasi dan pengembangan yang lebih baik.

7. Sederhana

   Algoritma pencarian sebaiknya sederhana dan tidak terlalu kompleks, sehingga dapat diimplementasikan dengan mudah. Algoritma yang sederhana akan memudahkan implementasi dan penggunaannya dalam program atau sistem.

Berikut adalah beberapa istilah dalam algoritma pencarian:

1. Pencarian. Proses mencari nilai tertentu dalam suatu kumpulan data.
2. Kumpulan data. Sekumpulan nilai yang disimpan dalam suatu struktur data, seperti array, linked list, atau tree.
3. Indeks. Nomor posisi suatu nilai dalam kumpulan data.
4. Pencarian linear. Metode pencarian yang dilakukan dengan memeriksa setiap elemen kumpulan data secara berurutan.
5. Pencarian biner. Metode pencarian yang hanya dapat dilakukan pada kumpulan data yang sudah diurutkan. Proses pencarian dilakukan dengan membagi kumpulan data menjadi dua bagian dan mencari di bagian yang relevan dengan nilai yang dicari.
6. Fungsi pencarian. Fungsi yang digunakan untuk mencari suatu nilai dalam kumpulan data.
7. Kompleksitas waktu. Ukuran kompleksitas algoritma dalam hal waktu, yaitu seberapa cepat algoritma dapat menyelesaikan masalahnya.
8. kompleksitas ruang. Ukuran kompleksitas algoritma dalam hal ruang, yaitu seberapa banyak memori yang diperlukan oleh algoritma untuk menyelesaikan masalahnya.
9. Algoritma brute force. Metode pencarian yang dilakukan dengan cara memeriksa semua kemungkinan nilai yang ada dalam kumpulan data.
10. Algoritma heuristik. Metode pencarian yang dilakukan dengan cara mencari solusi secara berurutan dan mengambil keputusan yang terbaik di setiap langkahnya.