Algoritma linear search
Linear search adalah algoritma pencarian nilai tertentu pada sebuah array/list. Algoritma pencarian ini melibatkan pemeriksaan nilai elemen pada list satu demi satu dari ujung list. Karena mekanisme kerjanya, algoritma ini juga dikenal juga dengan nama lain sequential search. Algoritma ini cocok digunakan pada array/list dengan nilai yang tidak terurut. Untuk array/list terurut, akan lebih efisien bila menggunakan binary search.
Teknik implementasi algoritma ini dalam bahasa pemrograman python cukup sederhana. Pada artikel ini diperlihatkan dua teknik linear search yakni linear search biasa yang menggunakan for loop, dan sentinel linear search yang menggunakan while loop.
Linear search dengan for loop
Untuk cara ini, perhatikan dan jalankan kode di bawah, kemudian baca penjelasan atas kode tersebut.
Penjelasan:
- Baris pertama adalah deklarasi list dengan isi beberapa elemen.
- Baris kedua berisi elemen yang dicari.
- Variabel idx pada baris ketiga untuk menandai posisi elemen bila ditemukan. Variabel ini diisi dengan nilai awal -1.
- Perintah perulangan pada baris 5 s.d 8 memeriksa tiap elemen pada list, kemudian setelah elemen ditemukan idx diisi dengan nilai i (indeks saat ini) dan perulangan dihentikan dengan perintah break.
- Pada baris 10 s.d 13, jika idx masih terisi dengan nilai -1, berarti nilai yang dicari tidak ditemukan pada list. Sebaliknya, berarti nilai yang dicari ditemukan pada indeks yang sama dengan nilai idx.
Linear search dengan sentinel
Penggunaan sentinel pada algoritma ini pada dasarnya adalah cara untuk memastikan perulangan berhenti tanpa melewati elemen terakhir (out of bound), namun tanpa memerlukan pemeriksaan apakah indeks terakhir sudah terlewati, sehingga mengurangi beban perbandingan pada setiap iterasi. Hal ini dimungkinkan dengan menjadikan elemen yang dicari sebagai sentinel pada ujung array, yang secara praktis akan menghentikan perulangan jika sudah sampai pada posisi sentinel dimaksud (ujung array).
Implementasi sentinel linear search pada python dapat dilihat pada pada cuplikan kode di bawah ini. Perhatikan bahwa baris ke-4 elemen yang dicari ditambahkan sebagai sentinel dengan perintah append ke ujung akhir list.
Semoga bermanfaat,
Salam
