Pernahkah kalian merasa kebingungan saat mencari sebuah buku di lemari buku kalian? Atau bahkan di perpustakaan? Saat kalian meminta bantuan kepada petugas perpustakaan, mengapa dia dapat menemukan buku yang kalian cari dengan waktu yang lebih singkat? Suatu hari, kalian kehilangan baju seragam yang harus dipakai pada hari itu dan kalian mencarinya. Apa strategi kalian supaya baju tersebut cepat ditemukan?
Mencari adalah menemukan “sesuatu” yang bisa berupa benda, angka, konsep, informasi yang memenuhi kriteria tertentu dalam suatu ruang pencarian. Masalah pencarian sangat umum ditemukan di dalam kehidupan, termasuk dalam dunia komputasi. Ketika melakukan suatu pencarian, kalian harus menemukan suatu benda atau objek yang memenuhi kriteria tertentu dari sekumpulan benda atau objek lain.
Beberapa contoh dari masalah pencarian yang sering kalian temui ialah sebagai berikut.
Mencari buku dengan judul tertentu di rak buku perpustakaan.
Mencari pakaian batik seragam kalian di lemari yang berisi semua pakaian yang kalian miliki.
Mencari dokumen atau web tertentu dengan mesin pencari seperti Google.
Mencari benda nyata gampang, tinggal kita lihat dan kita cocokkan dengan mata. Namun, mencari informasi atau konsep yang tidak kelihatan? Hmmmmm… Tidak mudah!
Pertanyaan selanjutnya ialah bagaimana strategi untuk mencari. Banyak cara yang dapat kita lakukan, misalnya: kita dapat mengambil pakaian secara acak dan mengecek apakah pakaian tersebut ialah seragam batik. Cara lain, misalnya dengan memeriksa pakaian dari yang berada paling atas ke paling bawah. Tentunya, ada banyak strategi lain yang dapat kalian gunakan. Ada strategi yang lebih baik daripada strategi yang lain, bergantung pada keadaan benda atau objek tersebut saat pencarian dilakukan. Tentunya, kita akan lebih mudah mencari suatu buku dengan judul tertentu di lemari perpustakaan yang tersusun rapi dengan aturan tertentu dibandingkan dengan mencarinya di sebuah lemari yang berantakan.
Jenis-jenis Algoritma Pencarian
Pencarian Linear (Linear Search)
Pencarian Biner (Binary Search)
Pencarian Interpolasi
dan lain-lain
Jenis algoritma ini bekerja dengan menemukan elemen dalam daftar dengan memeriksa secara berurutan setiap elemen daftar hingga menemukan kecocokan atau menyelesaikan pencarian di seluruh daftar.
Algoritma pencarian linear dinilai tidak praktis, karena tingkat kecepatannya yang lambat. Akan tetapi, ini bisa menjadi pilihan yang baik jika diterapkan dalam kumpulan data yang kecil. Hal ini dikarenakan sekelompok data yang kecil tidak memerlukan penyortiran data terlebih dahulu.
Jika Anda memiliki sekelompok data yang cukup besar, penggunaan algoritma dan skema pencarian biner jauh lebih cepat dibandingkan dengan algoritma pencarian linear.
Jenis algoritma ini sangat berguna untuk menemukan posisi nilai tertentu dalam larik yang diurutkan. Algoritma pencarian biner dianggap sebagai salah satu algoritma pencarian paling efisien, karena memiliki tingkat kecepatan kerja yang tinggi.
Algoritma pencarian biner bekerja dengan mulai mencari di tengah array, kemudian turun ke bagian bawah atau atas dari urutan yang diberikan.
Apabila nilai median lebih rendah dari nilai target, pencarian akan dilanjutkan pada separo data yang lebih tinggi.
Jika sebaliknya, pencarian akan dilanjutkan pada separo data yang lebih rendah.
contoh :
Banyak data : 20
Data : 2, 3, 4, 7, 8, 10, 11, 13, 14, 16, 17, 18, 19, 21, 22, 25, 26, 31, 32, 36.
Target pencarian : 19
Langkah-langkah pencarian biner :
nilai tengah : data ke-[(1+20)/2] --> data ke-11
data ke[11] = 17 < 19
maka pencarian berikutnya adalah data ke[12] hingga data ke[20]
Data : 2, 3, 4, 7, 8, 10, 11, 13, 14, 16, 17, 18, 19, 21,22, 25, 26, 31, 32, 36.
nilai tengah : data ke-[(12+20)/2] --> data ke[16]
data ke[16] = 25 > 19
maka pencarian berikutnya adalah data ke[12] hingga data ke[15]
Data : 2, 3, 4, 7, 8, 10, 11, 13, 14, 16, 17, 18, 19, 21, 22, 25, 26, 31, 32, 36.
nilai tengah : data ke-[(12+15)/2] --> data ke-14
data ke[14] = 21 > 19
maka pencarian berikutnya adalah data ke[12] hingga data ke[13]
Data : 2, 3, 4, 7, 8, 10, 11, 13, 14, 16, 17, 18, 19, 21,22, 25, 26, 31, 32, 36.
nilai tengah : data ke-[(12+13)/2] --> data ke-13
data ke[13] = 19 = 19 (target) --> ketemu
pencarian selesai
Data : 2, 3, 4, 7, 8, 10, 11, 13, 14, 16, 17, 18, 19 , 21,22, 25, 26, 31, 32, 36.