Algoritma - Pencarian Berurut

Pada materi algoritma kali ini kita masuk pada pembahasan mengenai searching. Algoritma pencarian atau algoritma searching merupakan proses pengolahan data dalam menemukan nilai atau data tertentu, dengan menerima input sebagai masalah dan menghasilkan output sebagai solusi. Kita bisa menemukan algoritma baik dalam bentuk internal search, artinya algoritma pencarian dilakukan dalam memori komputer atau dalam bentuk external search, algoritma pencarian dilakukan dengan menambah external media untuk menambah main memory.

Secara simplenya, seseorang atau user punya masalah, memberikan input sebuah key, nah algoritma akan berjalan dengan menemukan record pada list yang tersedia. Efektif atau tidaknya tergantung algoritma pencarian apa yang dilakukan.

Baik sebelum kita lanjut, kita pahami dulu, meskipun beberapa sudah kita bahas dimateri sebelumnya, apa itu key, apa itu Big O Notasi. Key merupakan sebuah input dari suatu data yang digunakan sebagai pembanding selama proses pencarian. Big O notasi, merupakan notasi yang mengindikasi kenaikan atau dikenal sebagai order of growth unjuk kerja dari algoritma pencarian. Terdapat record yang tersimpan dalam list dan memiliki sebuah asosiasi key. Ketika ingin melakukan pencarian, yang dilakukan adalah memasukkan input key, kemudian menemukan elemen dalam koleksi di memori utama atau pada disk, dimana koleksi berupa semisal (K1,I1),(K2,I2),……(Kn,In). Anda atau user memberi query berupa (I,K) lokasi (I1,K1): K1 = K. Hasil pencarian akan berhenti ketika menemukan record yang sesuai key atau berhenti karena tidak ditemukannya record.

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. Algoritma pencarian (searching algorithm) adalah algoritma yang menerima sebuah argumen kunci dan dengan langkah-langkah tertentu akan mencari rekaman dengan kunci tersebut. Setelah proses pencarian dilaksanakan, akan diperoleh salah satu dari dua kemungkinan, yaitu data yang dicari ditemukan (successful) atau tidak ditemukan (unsuccessful).

Algoritma pencarian terdapat beberapa metode, dan kali ini diawali dengan pembahasan tentang Algoritma Sequential Search. Algoritma ini merupakan teknik pencarian data dari array yang paling mudah. Data dalam array dibaca 1 demi satu, diurutkan dari index terkecil ke index terbesar, maupun sebaliknya. Pencarian sangat sederhana dengan mencari item tertentu di dalam list. Kemudian beroperasi secara perulangan pada setiap elemen O(n) sampai menemukan record berdasar key atau akhir tercapai. Konsep dasar algoritma ini dengan melakukan perbandingan antara data key dengan data lainnya sampai data tersebut ditemukan atau tidak.

Kelemahan algoritma ini dengan kasus yang paling buruk, dimana N elemen data harus dilakukan pencarian sebanyak N kali juga sehingga prosesnya adalah:

(1) i ← 0 
(2) found ← false 
(3) Selama (not found) dan (i <= N) lakukan baris 4 
(4) Jika (Data[i] = x) maka found ← true, jika not found i ← i + 1 
(5) Jika (found) maka i adalah indeks dari data yang dicari, jika tidak
Not found! 

Contohnya anda punya record dalam list

List:

box1

box2

box3

Sequential Search dapat dengan mudah dilihat sebagai O(n) dalam kasus yang terburuk (ketika key tidak dalam array) dan kasus rata-rata.

Dalam kasus pencarian tidak berhasil – not found!, ada n + 1 melewati loop (key dibandingkan dengan semua i = 0..n, tes berhasil hanya dalam posisi dummy n). Nah kondisi yang mesti dilakukan pengecekan terhadap elemen array (n record) adalah record yang dicari berada pada posisi terakhir array. Setelah pengecekan seluruh elemen array, ternyata record yang dicari tidak berhasil ditemukan dalam array tersebut.

Dalam kasus pencarian sukses, key dapat ditemukan di salah satu dari n posisi i = 0 .. n - 1 dengan probabilitas yang sama. Jika key ditemukan dalam posisi dengan, i+1 perbandingan akan dibuat.

Sequential Search dapat dibuat lebih efisien jika array diurutkan karena pencarian kemudian dapat dihentikan atau not found! ketika elemen yang lebih besar dari key pencarian ditemukan. Ada berbagai teknik heuristik yang dapat digunakan untuk mempercepat algoritma Sequential Search. Sebagai contoh, record yang paling sering diakses dapat disimpan ke awal list, atau jika informasi tentang frekuensi relatif dari akses tidak tersedia pengaturan optimal ini dapat diperkirakan dengan memindahkan record ke awal list setiap kali diakses. Namun tidak satu pun dari teknik ini akan meningkatkan efisiensi prosedur pencarian di luar O (n).

Oke sampai disini dulu pembahasan kita tentang Algoritma Sequential Search, pembahasan algoritma searching lainnya akan kita lanjutkan dimateri berikutnya