Searching Algorithms
SEARCHING
SEARCHING ALGORITHM
Searching atau pencarian merupakan proses menemukan suatu value atau suatu data pada sekumpulan atau sekelompok data yang memiliki tipe yang sama[1]. Data yang dapat dicari mulai dari tipe data integer, tipe data string, tipe data char, tipe float, dan tipe data lainnya asalkan data tersebut dapat dibandingkan atau dicompare satu sama lain. Untuk mencari suatu data dalam sekumpulan data, terdapat beberapa metode yang dapat digunakan untuk dapat mengimplementasikan algoritma searching ini. Dua dari banyak metode tersebut antara lain, algoritma sequential search dan algoritma binary search[1]. Setelah algoritma tersebut selesai dijalankan maka kita akan mendapatkan atau memperoleh salah satu dari dua kemungkinan yaitu antara data ditemukan (sukses) atau data tidak ditemukan (gagal).
METODE SEARCHING
Seperti yang disebutkan sebelumnya, pada searching terdapat 2 metode pencarian yaitu metode sequential search dan metode binary search. Yang membedakan diantara dua metode ini ialah cara algoritma tersebut untuk membandingkan dan mencari suatu data.
Sequential Search (Pencarian Beruntun atau Lurus)
Sesuai dengan namanya, pada algoritma pencarian beruntun akan dilakukan perbandingan data secara berturut-turut satu per satu hingga data tersebut ditemukan atau hingga data terakhir jika data yang dicari tersebut tidak ditemukan[1], [2]. Metode pencarian ini merupakan metode pencarian yang paling sederhana karena hanya berbasis pada perulangan dan perbandingan atau komparasi antar data[1]. Operasi yang dilakukan dalam algoritma sequential search ini adalah perulangan yang dilakukan sebanyak jumlah data yang tersedia kemudian dalam setiap perulangan tersebut data yang akan dicari dibandingkan dengan data yang ada pada posisi perulangan saat ini[1]. Misalnya data yang dicari dibandingkan data ke-i dimana ‘i’ merupakan nomor urut perulangan yang dilakukan. Jika data ke-i tersebut sama dengan data yang akan dicari maka akan dilakukan aksi bahwa data tersebut telah ditemukan, sedangkan jika data tidak ditemukan hingga data yang terakhir maka data yang dicari tidak ditemukan[1].
Karena berbasis pada perulangan yang berjalan secara linear atau lurus dan berturut-turut, sequential search dianggap tidak efektif karena dapat memakan waktu yang banyak tergantung dengan jumlah data yang ada, sequential search sendiri memiliki time complexity sebesar Big O(n), sehingga dalam kasus terburuk (worst case) program akan melakukan perulangan dan perbandingan sebanyak n-kali, dimana hal tersebut akan memakan banyak waktu[1].
Binary Search (Pencarian Bagi Dua)
Algoritma binary search adalah salah satu dari beberapa algoritma searching. Binary search merupakan sebuah algoritma yang lebih efisien yang digunakan untuk mencari suatu value ataupun item dari sekumpulan data yang sudah terurut[3]. Algoritma ini bekerja dengan membagi dua berulang kali kumpulan data yang kemungkinan mengandung value atau data yang ingin dicari. Biasanya, binary search digunakan untuk mencari value atau item pada sebuah array. Apabila kumpulan data tersebut dalam keadaan belum terurut maka algoritma ini tidak dapat diimplementasikan[3]. Contoh cara kerja algoritma ini ialah sebagai berikut: Misalkan, kita mempunyai array terurut seperti dibawah ini:
Misalkan kita ingin mencari angka 12 pada array, anda dapat membagi dua array tersebut:
Subarray 1
Subarray 2
Setelah itu, bandingkan angka 12 dengan elemen terakhir dari array. Apabila lebih kecil, maka data akan dicari pada subarray 1 dan subarray 2 tidak perlu lagi dihiraukan. Sedangkan apabila lebih besar, maka data akan dicari pada subarray 2 dan subarray 1 sudah tidak perlu lagi dihiraukan. Proses diatas diulangi lagi pada subarray yang dicari. Subarray 2 dibagi lagi menjadi 2 hingga menghasilkan subarray seperti dibawah ini:
Subarray 2.1
Subarray 2.2
Kemudian, kita bandingkan lagi seperti sebelumnya. Apabila 12 lebih kecil dari elemen terakhir dari subarray 2.1 maka data akan dicari pada subarray 2.1 dan sub array 2.2 tidak perlu dihiraukan lagi. Sedangkan apabila nilai 12 lebih besar dari elemen terakhir dari subarray 2.2 maka data akan dicari pada subarray 2.2. Seperti sebelumnya, proses diulangi pada subarray yang dicari hingga menemukan data 12.
Subarray 2.2.1
Subarray 2.2.2
Karena subarray 2.2.1 hanya memiliki 1 elemen dan itu sama dengan 12 maka pada iterasi ini, data yang kita cari sudah dapat ditemukan. Alasan mengapa binary search dikatakan sebagai algoritma yang efisien dibandingkan dengan sequential search karena apabila menggunakan sequential search pada kasus di atas maka akan membutuhkan 7 iterasi untuk menemukan angka 12. Sedangkan apabila menggunakan algoritma binary search, dibutuhkan sebanyak 5 iterasi untuk dapat menemukan angka 12. Hal ini hanya berlaku pada kumpulan data yang sudah terurut karena apabila datanya belum terurut maka algoritma binary search tidak dapat diimplementasikan.
PENERAPAN SEARCHING
Mungkin dari kalian masih ada yang bingung bagaimanakah cara mengimplementasikan konsep searching ini pada suatu permasalahan. Maka dari itu, berikut merupakan contoh pengimplementasian konsep searching untuk mencari suatu value pada kumpulan data. Misalkan, anda memiliki kumpulan data yang telah anda kumpulkan dan anda input dalam bentuk array sebagai berikut:
Lalu misalkan anda tinggalkan data ini selama beberapa hari dan kemudian anda lupa dengan data data apa saja yang telah anda masukkan pada array tersebut. Lalu anda ingin memastikan atau mencari apakah data 6 terdapat pada array tersebut sehingga anda memutuskan untuk mengimplementasikan algoritma searching. Pertanyaannya disini ialah, algoritma mana yang harus anda pilih agar pencariannya dapat memakan waktu yang lebih cepat sehingga lebih efisien. Apabila anda, hanya menginginkan untuk mencari suatu data tanpa mementingkan waktu pencariannya maka anda dapat memakai algoritma manapun yang yang dimana arraynya harus memenuhi syarat dari algoritma tersebut. Namun apabila anda ingin mencari data dengan waktu yang lebih efisien, anda harus memilih algoritma yang tepat.
1. Menggunakan Sequential Search
Array
Apabila kita lihat array data sebelumnya, terlihat bahwa data yang dimasukkan merupakan data yang belum terurut sehingga anda tidak dapat mengimplementasikan algoritma binary search sebelum data pada array tersebut terurut. Jadi, algoritma yang kita pakai dalam kasus ini pertama adalah algoritma sequential search. Jadi array tidak perlu diurutkan. Dimulai dari indeks 0, program harus membandingkan apakah nilai yang disimpan dalam array indeks tersebut sama dengan nilai yang kita cari. Apabila valuenya sama maka dapat dipastikan bahwa data yang anda cari dapat ditemukan. Apabila tidak ditemukan maka pengecekan dilanjutkan pada indeks berikutnya hingga indeks terakhir. Apabila hingga indeks terakhir tidak ditemukan data yang sama dengan yang anda cari maka dapat dipastikan bahwa data yang anda cari tidak dapat ditemukan.
Misalkan, pada array di atas, kita ingin mencari angka “6”. Maka program akan mengecek dari indeks ke 0 hingga data ditemukan ataupun hingga indeks terakhir. Karena pada indeks ke 8 ditemukan value yang sama dengan “6” maka dapat dipastikan bahwa value yang anda cari dapat ditemukan.
2. Menggunakan Binary Search
Kita sebelumnya sudah melihat bagaimana sequential search diimplementasikan pada array yang tidak terurut. Namun, apabila data yang dimasukkan ke array tersebut terurut dengan benar maka anda dapat mengimplementasikan algoritma binary search dibandingkan sequential search agar waktu pencariannya lebih efisien. Misalkan, data yang dimasukkan tersebut terurut seperti ini:
Array
Lalu, anda ingin mencari value “6”. Pertama tama, anda harus membagi menjadi 2 bagian array tersebut. Sehingga array diatas menjadi dua bagian seperti dibawah ini:
Subarray 1
Subarray 2
Karena nilai “6” lebih besar dari elemen terakhir subarray 1 maka data akan dicari pada subarray 2. Lalu subarray dibagi lagi menjadi dua bagian sehingga menjadi seperti dibawah ini:
Subarray 2.1
Subarray 2.2
Karena nilai “6” lebih besar dari nilai elemen terakhir dari subarray 2.1 maka data akan dicari pada subarray 2.2. Lalu subarray 2.2 dibagi menjadi dua bagian sehingga menjadi seperti dibawah:
Subarray 2.2.1
Subarray 2.2.2
Karena nilai “6” sama dengan nilai dari elemen pada subarray 2.2.1 maka dapat dipastikan bahwa data yang anda cari tersebut ditemukan. Dengan menggunakan algoritma binary search, membutuhkan sebanyak 4 iterasi. Apabila pada data tersebut diatas menggunakan sequential search, maka akan membutuhkan sebanyak 10 iterasi untuk dapat menemukan nilai “6” pada array. Hal tersebut lah yang menyebabkan algoritma binary search lebih efisien dari sequential search. Namun kembali lagi, pemilihan algoritma tersebut bergantung pada kondisi kondisi tertentu sehingga anda harus dengan cermat memilih algoritma atau metode yang ingin digunakan.
IDENTITAS PENULIS
Instansi : Universitas Udayana (www.unud.ac.id)
Kelompok : D3 / Informatika
Anggota : Muhammad Syarief Hidayatullah (2008561014)
Qaris Ardian Pratama (2008561034)
Gede Gery Sastrawan (2008561039)
Kadek Yoga Vidya Pradnyditha (2008561069)
I Kadek Riski Ari Putra (2008561079)
DAFTAR PUSTAKA
[1] Thomas Cormen dan Devin Balkcom, “Binary search,” khanacademy.org, 2014. [Online]. Available: https://www.khanacademy.org/computing/computer-science/
algorithms/binary-search/a/binary-search [Accessed Dec. 10, 2021].
[2] S, Jain. “Searching Algorithms”. Geeksforgeeks.org. 2021. [Online] Available: https://www.geeksforgeeks.org/searching-algorithms/ [Accessed Dec. 10, 2021].
[3] Anonymous. “Analisis Algoritma,” https://catatananalgo.wordpress.com/. 2016. [Online] Available: https://catatananalgo.wordpress.com/2016/10/02/algoritma-sear
ching-pencarian/ [Accessed Dec. 10, 2021].
Comments
Post a Comment