Dalam jaringan komunikasi yang berkembang pesat saat ini, bisnis beralih ke digital untuk meningkatkan efisiensi manajemen. Dengan meningkatnya jumlah data yang dihasilkan di internet, kumpulan data menjadi lebih kompleks. Untuk mengatur, mengelola, mengakses, dan menganalisis data secara hati-hati dan efisien, penggunaan struktur data sangatlah penting.
Postingan sebelumnya telah dibahas berbagai jenis struktur data maupun metode algoritmanya. Postingan kali ini kita akan membahas mengenai Searching. Apa itu searching? Yuk kita pelajari bareng-bareng.
Pengertian Searching
Searching adalah proses mendapatkan (retrieve) information berdasarkan kunci (key) tertentu dari sejumlah informasi yang telah disimpan. Kunci (key) digunakan untuk melakukan pencarian record yang diinginkan didalam suatu list.
Searching dalam pemrograman merupakan proses yang sangat fundamental guna mencari data tertentu dalam sekumpulan data tentunya yang memiliki tipe yang sama. Pencarian diperlukan untuk mencari informasi khusus dari tabel/kumpulan data pada saat lokasi yang pasti dari informasi tersebut sebelumnya tidak diketahui. Data pada tabel biasanya disimpan dengan menggunakan tipe data Array yang dimana Array memungkinkan untuk menyimpan nilai yang bertipe sama.
Metode Searching
1. Sequential Search
Sequential Searching sebuah metode pencarian yang Konsepnya membandingkan sekumpulan elemen data yang ada dengan mengeceknya satu-persatu dari awal sampai akhir apakah data tersebut ditemukan atau tidak.
Sequential Searching merupakan teknik yang sederhana dan langsung dapat digunakan pada struktur data baik array maupun linked-list. Pencarian data secara urut mulai dari data pertama sampai kunci yang dicari ditemukan atau sampai seluruh data telah dicari dan tidak ditemukan. Sequential Search dilakukan pada data yang tidak terurut.
Algoritma Sequential Search
- Input x (data yang dicari)
- Bandingkan x dengan data ke-i sampai n
- Jika ada data yang sama dengan x maka cetak pesan “Ada”
- Jika tidak ada data yang sama dengan x cetak pesan “tidak ada”
Best & Worst Case
- Best case : jika data yang dicari terletak di depan sehingga waktu yang dibutuhkan minimal.
- Worst case : jika data yang dicari terletak di akhir sehingga waktu yang dibutuhkan maksimal.
Contoh :
DATA = 5 6 9 2 8 1 7 4
bestcase ketika x = 5
worstcase ketika x = 4
*x = key/data yang dicari
2. Binary Searching
Binary Searcing adalah metode dengan prinsip dasarnya adalah melakukan proses pembagian ruang pencarian secara berulang-ulang sampai data ditemukan atau sampai ruang pencarian tidak dapat dibagi lagi (berarti ada kemungkinan data tidak ditemukan). Metode ini memperkecil jumlah operasi pembandingan yang harus dilakukan antara data yang dicari dengan data yang ada di dalam tabel, khususnya untuk jumlah data yang sangat besar ukurannya. Syarat dalam metode ini adalah data sudah dalam keadaan terurut (naik) ascending.
Adapun Cara Kerja Metode Binary Searching dalam Struktur data seperti berikut :
- Kunci akan selalu dibandingkan dengan data yang berada di tengah (middle)
- Bila sama berarti data ketemu, bila tidak, akan “dilihat” apakah data ada di sebelah “kiri” (artinya data lebih kecil dari data di tengah) atau di sebelah “kanan” (artinya data lebih besar dari data di tengah).
- Bila data ada di sebelah kiri, dilakukan pencarian dengan cara yang sama (sementara data yang berada di sebelah kanan akan diabaikan).
- Jadi, setiap kali pencarian, data selalu “dibelah” menjadi dua bagian (biner), sampai pada “titik tertentu”(bila sama dengan titik tengah, pencarian tidak dilakukan lagi, bila tidak, lakukan pencarian lagi sampai pada perbandingan terakhir data juga tidak sama, berarti data tidak ditemukan pada array).
Teknik Binary Search hanya dapat digunakan pada sorted array, yaitu array yang elemen-elemennya telah terurut.
Binary Search:
- Lebih cepat dari sequential search
- Teknik pencarian = data dibagi menjadi dua bagian untuk setiap kali proses pencarian.
- Data awal harus dalam kondisi terurut. Sehingga harus dilakukan proses sorting terlebih dahulu untuk data awal.
- Mencari posisi tengah : Posisi tengah = (posisi awal + posisi akhir) / 2
Algoritma Binary Search
- Data diambil dari posisi awal 1 dan posisi akhir N
- Kemudian cari posisi data tengah dengan rumus: (posisi awal + posisi akhir) / 2
- Kemudian data yang dicari dibandingkan dengan data yang di tengah, apakah sama atau lebih kecil, atau lebih besar?
- Jika data sama, berarti ketemu.
- Jika lebih besar, maka ulangi langkah 2 dengan posisi awal adalah posisi tengah + 1
- Jika lebih kecil, maka ulangi langkah 2 dengan posisi akhir adalah posisi tengah – 1
Best & Worst Case
- Best case : jika data yang dicari terletak di posisi tengah.
- Worst case : jika data yang dicari tidak ditemukan.
Contoh :
DATA = 5 6 9 2 8 1 7 4 3
bestcase ketika x = 8 (T(n)=1)
worstcase ketika x = 25 (T(n) = 5 atau n/2)
*x = key/data yang dicari
3. Interpolation Search
Interpolation Search adalah salah satu algoritma pencarian yang merupakan pengembangan dari algoritma Binary Search. Pencarian dilakukan pada posisi relatif kunci terhadap data yang terurut. Metode ini didasari pada proses pencarian nomor telepon pada buku telepon.
