Jenis 1: data diskret
Biasanya kita diberikan sebuah array terurut berisi N nilai, lalu diminta mencari index untuk suatu nilai v.Implementasi yang saya sukai adalah secara iteratif, menggunakan while. Representasikan rentang pencarian dengan dua variabel, sebut saja l dan r. Selama rentang pencarian tidak kosong (yaitu l <= r), periksa nilai di tengah. Kalau nilai di tengah sama dengan v, hentikan pencarian. Kalau lebih kecil, geser batas bawah rentang pencarian menjadi 1 indeks setelah bagian tengahnya. Kalau lebih besar, geser batas atas rentang pencarian menjadi 1 indeks sebelum bagian tengah.
Berikut implementasi lengkapnya. Kalau sampai keluar dari while dan variable ans masih bernilai -1, artinya nilai v tidak ditemukan.
Variasi lain yang memusingkan adalah kalau v tidak ditemukan, cari nilai terdekat yang lebih besar.
Solusinya sama seperti sebelumnya, kecuali ketika nilai di tengah mungkin menjadi jawaban, catat indeksnya. Setelah rentang pencarian habis, dijamin indeks terakhir yang dicatat menyimpan jawaban yang diinginkan. Berikut implementasinya:
Apabila nilai v tidak ditemukan dan yang diinginkan adalah nilai terdekat yang lebih kecil, cukup ubah kondisinya:
Kedua variasi ini adalah binary search yang akan sering Anda temukan pada kompetisi. Pastikan Anda hafal kapan jawaban perlu dicatat.
Jenis 2: Data Kontinu
Biasanya kita tidak diberikan array berisi data, melainkan kita diminta menebak suatu bilangan riil yang memenuhi suatu kondisi. Anggap saja kita memiliki fungsi f, yang menerima bilangan riil antara 0 sampai 1 dan mengembalikan true jika dan hanya jika kondisi terpenuhi. Lalu anggap fungsi f ini memiliki sifat khusus, yaitu terdapat suatu bilangan v, sehingga setiap x yang memenuhi x≥v pasti memiliki nilai f(x) bernilai true.Sama seperti sebelumnya, buat dua variabel yang merepresentasikan rentang pencarian.
Lalu terdapat setidaknya dua pandangan tentang implementasinya, yaitu menggunakan while sampai rentang pencarian hampir tidak berubah lagi seperti berikut:
Pada implementasi di atas, dipilih nilai 10-8 sebagai nilai toleransi. Kalau beda rentang pencarian sudah lebih kecil dari nilai tersebut, pencarian dianggap selesai dan l dianggap sebagai jawabannya.
Pandangan implementasi lainnya adalah dengan menggunakan for sebanyak K kali. Nilai K biasanya 100, yang mana sudah sangat akurat:
Secara pribadi saya lebih menyukai strategi yang menggunakan for. Alasannya adalah dijamin setelah 100 langkah, program akan berhenti; sementara untuk strategi dengan while, tidak ada jaminan kapan program berhenti. Saya selalu menggunakan strategi dengan for dan tidak pernah ada masalah.
Tidak ada komentar :
Posting Komentar