Searching (pencarian) merupakan proses yang fundamental dalam pengelolaan data. Proses pencarian adalah menemukan nilai (data) tertentu didalam sekumpulan data sama (baik bertipe data dasar atau bertipe bentukan).
Metode searching
Sequential search
Sequential searching atau pencarian beruntun adalah proses membandingkan setiap elemen atau larik satu persatu secara beruntun mulai dari elemen pertama sampai elemen yang dicari ditemukan atau seluruh elemen sudah diperiksa.
Sequential search terbagi dua, yaitu :
Sequential search tanpa boolean
-Tanpa sentinel
• Tidak menggunakan variabel boolean
• Tidak mempunyaintambahan elemen di akhir array
Contoh :
Angka | 5 | 1 | 9 | 4 | 2 |
| 1 | 2 | 3 | 4 | 5 |
Data yang dicari : 4
-Angka(1) = 4? F
-Angka(2) = 4? F
-Angka(3) = 4? F
-Angka(4) = 4? T
Maka data yang dicari ditemukan pada indeks ke-4
-Dengan sentinel
• Tidak menggunakan variabel boolean
• Mempunyai tambahan elemen di akhir array untuk menyimpan data cari apabila data cari tidak ditemukan
Contoh :
Angka | 5 | 1 | 9 | 4 | 2 | 10 | --> Sentinel
| 1 | 2 | 3 | 4 | 5 | 6 |
Data yang dicari : 10
-Tempatkan data yang dicari pada sentinel
-Telusuri array seperti sequential search tanpa sentinel, jika data ditemukan pada sentinel, maka data yang dicari tidak ada/tidak ditemukan, tapi jika data yang dicari ditemukan bukan pada sentinel, maka data yang dicari ditemukan.
Sequential search dengan boolean
• Menggunakan variabel boolean
• Menghasilkan nilai TRUE atau FALSE diakhir pencarian.
Contoh :
Angka | 5 | 1 | 9 | 4 | 2 |
| 1 | 2 | 3 | 4 | 5 |
Data yang dicari : 9
Proses pencariannya sama seperti proses pencarian pada metode sequential search lainnya, hanya saja melibatkan sebuah variabel lain yang bertipe boolean.
Binary Search
Binary searching yaitu metode pencarian bagi dua. Metode ini digunakan untuk kebutuhan pencarian dengan waktu yang cepat. Data yang disimpan didalam larik harus sudah terurut.
Algoritma
1. Data harus terurut baik secara ascending maupun descending
2. Mekanismenya adalah dengan cara membagi larik menjadi dua bagian yaitu bagian kiri (indeks terkecil/Ia) sampai indeks ke bagian tengah dan bagian kanan mulai dari indeks tengah sampai indeks terbesar (Ib)
3. Indeks tengah (k) : (Ia)+(Ib) div 2 (posisi tengah larik)
4. Jika data yang dicari lebih kecil dari data tengah maka pencarian dilanjutkan ke bagian kiri
5. Jikan data yang dicari lebih besar dari data tengah maka pencarian dilanjutkan ke bagian kanan.
Contoh :
Proses dengan cara membagi larik menjadi dua bagian (bagian kiri dan bagian kanan), dan mengecek data diposisi tengah apakah sama atau tidak dengan data yang dicari , jika tidak proses pencarian akan dilanjutkan ke bagian larik bagian kiri atau bagian kanan.
Misalkan, diberikan data sebagai berikut :
Angka | 3 | 7 | 12 | 15 | 29 |
| 1 | 2 | 3 | 4 | 5 |
Data yang di cari : 7
Catatan : data harus sudah terurut
Langkah 1: bagi larik menjadi dua bagian untuk mencari posisi tengah (k) dengan cara indeks atas (Ia)dijumlahkan dengan indeks bawah (Ib) lalu dibagi 2.
k = (Ia+Ib) div 2
= (1+5) div 2
= 3
| 3 | 7 | 12 | 15 | 29 |
| 1 | 2 | 3 | 4 | 5 |
(Ia) (k) (Ib)
Bagian Kiri Bagian kanan
Langkah 2 : Periksa data diposisi tengah larik (12), lalun bandingkan apakah sama atau tidak (12=7? F) , karena tidak sama maka akan diperiksa apakah data diposisi tengah lebih kecil daripada data yang dicari (12<7 ? F) karena lebih besar maka pencarian dilanjutkan kebagian kiri dengan cara menarik indeks bawah ke kiri (Ib = k-1)
| 3 | 7 |
| 1 | 2 |
(Ia) (Ib)
Hitung kembali titik tengah dari larik yang ditinjau (didapat k = 1)
| 3 | 7 |
| 1 | 2 |
(Ia) (Ib)
(k)
Langkah 3 : Ulangi langkah 1 s/d langkah 2 sampai data ditemukan atau sampai harga Ia > Ib
Angka 7 ditemukan pada indeks ke-2.
Sumber :
- http://darasinta.blogspot.co.id/2010/12/algoritma-searching.html
- Slide powerpoint Algoritma dan pemrograman searching Tim Algoritma dan Pemrograman Universitas Komputer Indonesia
0 komentar:
Posting Komentar