Pencarian Biner
Jawab banyak pertanyaan posisi pada daftar terurut dengan cepat.
Kamus tebal tidak dibaca dari halaman pertama saat mencari kata. Kita membukanya di tengah, lalu memilih separuh kiri atau kanan. Begitu juga komputer mencari di data yang sudah terurut.
Masukan
Baris pertama berisi N (1 sampai 20000). Baris kedua berisi N bilangan terurut naik, boleh ada yang sama. Baris ketiga berisi Q (1 sampai 20000). Baris keempat berisi Q bilangan yang dicari.
Keluaran
Satu baris berisi Q jawaban yang dipisah spasi. Setiap jawaban adalah posisi pertama bilangan itu di daftar (dihitung dari 1), atau -1 bila tidak ada.
Contoh masukan dan keluaran
Contoh 1
Masukan
7 2 4 4 4 7 9 12 4 4 12 5 2
Keluaran
2 7 -1 1
Petunjuk
Coba kerjakan dulu. Buka petunjuk satu per satu kalau kamu buntu.
Petunjuk 1
Mencari satu per satu untuk 20000 pertanyaan butuh sekitar 400 juta pemeriksaan, terlalu lama.
Petunjuk 2
Pencarian biner menyimpan batas kiri dan kanan. Bila nilai tengah lebih kecil dari yang dicari, buang separuh kiri. Selain itu, buang separuh kanan tetapi tetap ingat posisi tengah itu sebagai kandidat jawaban.