Pencarian dengan BINARY SEARCH
10/01/2013 19:44
Prinsip dari pencarian biner dapat dijelaskan sebagai berikut : mula-mula diambil posisi awal 0 dan posisi akhir = N - 1, kemudian dicari posisi data tengah dengan rumus (posisi awal + posisi akhir) / 2. Kemudian data yang dicari dibandingkan dengan data Jika lebih kecil, proses dilakukan kembali tetapi posisi akhir dianggap sama dengan posisi tengah –1. Jika lebih besar, porses dilakukan kembali tetapi posisi awal dianggap sama dengan posisi tengah + 1. Demikian seterusnya sampai data tengah sama dengan yang dicari.
Untuk lebih jelasnya, perhatikan algoritma berikut:
- Low = 1 , High = N
- Ketika Low <= High Maka kerjakan langkah No .3, Jika tidak Maka kerjakan langkah No.7
- Tentukan Nilai Tengah dengan rumus mid = ( Low + High ) Div 2
- Jika X < Nil. Tengah Maka High = Mid –1
- Jika X > Nil. Tengah Maka Low = Mid +1
- Jika X = Nil. Tengah Maka Nil. Tengah = Nil. Yg dicari
- Jika X > High Maka Pencarian GAGAL
Keterangan: X adalah nilai yang dicari.
Contoh Soal: Perhatikan deret bilangan berikut:
| Deret | 4 | 5 | 7 | 8 | 15 | 20 | 25 |
| Index | 1(Low) | 2 | 3 | 4 | 5 | 6 | 7(High) |
X=15 (bilangan yang dicari)
Jawab:
Tentukan nilai tengah (Mid) terlebih dahulu. Mid= (Low+High)/2 --> (1+7)/2=4, berarti nilai tengah (Mid) ada diindex 4 yaitu 8. Kemudian lakukan perbandingan (lihat langkah ke-4).
| Deret | 4 | 5 | 7 | 8 | 15 | 20 | 25 |
| Index | 1(Low) | 2 | 3 | 4(Mid) | 5 | 6 | 7(High) |
15 < 8 (Tidak), berarti nilai yang dicari (X) lebih besar dari nilai tengah (Mid). Lihat langkah ke-5 (algoritma diatas). Sehingga Low=Mid+1, berdasarkan ekpsresi perhitungan ini, jadi letak Low index-nya berpindah (Mid+1) artinya bergeser kekanan. dan urutanyya menjadi:
| Deret | 15 | 20 | 25 |
| Index | 5(Low) | 6 | 7(High) |
Cari nilai tengahnya lagi (Mid). Mid=(Low+High)/2 --> (5+7)/2=6, berarti nilai tengah (Mid) ada diindex 6 yaitu 20. Karena belum ditemukan, lakukan perbandingan (lihat langkah ke-4 kembali).
| Deret | 15 | 20 | 25 |
| Index | 5(Low) | 6(Mid) | 7(High) |
15<20 (Ya), maka nilai High=Mid-1. Sehingga deret bilangannya sekarang hanya tinggal 15 saja. Karena bilangannya hanya tinggal satu, tentu saja bilangan itu meliputi semua bagian Low,Mid,High,dan X (nilai yang dicari). Sehingga pencarian SUKSES.
| Deret | 15 |
| Index | Low,Mid,High,dan X (nilai yang dicari) |