Pencarian eksponensial
Pencarian biner perlu tahu di mana daftar berakhir sebelum bisa melihat ke tengah. Pencarian eksponensial tidak: ia melaju ke depan dengan langkah yang makin besar sampai melewati target, lalu menjalankan pencarian biner pada langkah terakhir. Itu membuatnya ideal untuk daftar yang panjangnya tidak diketahui, dan cepat untuk nilai di dekat awal.
Idenya
Periksa nilai di tempat 1, lalu 2, 4, 8, 16, dan seterusnya, setiap tempat dua kali yang sebelumnya. Selama nilai di sana lebih kecil dari target, target pasti ada lebih jauh. Saat pertama kali ada nilai yang tidak lebih kecil, target terkurung: ia ada setelah tempat yang diperiksa sebelumnya dan tidak lebih jauh dari tempat ini. Rentang itu terurut, jadi pencarian biner menemukan target, atau menunjukkan bahwa target tidak ada.
Contoh
Cari 23 dalam 2, 5, 8, 12, 16, 23, 38, 56, 72, 91. Tempat 1 berisi 2, tempat 2 berisi 5, tempat 4 berisi 12, semuanya lebih kecil. Tempat 8 berisi 56, yang lebih besar, jadi 23 hanya bisa ada di tempat 5 sampai 7. Pencarian biner memeriksa tengahnya, tempat 6, dan menemukan 23: 5 perbandingan, sedangkan pencarian biner biasa perlu 3. Mencari 12 dalam daftar yang sama berhenti di tempat 4 setelah 3 perbandingan, satu lebih sedikit daripada pencarian biner, dan 2 ditemukan di tempat 1 dengan satu perbandingan saja.
Berapa banyak perbandingan
Untuk target di tempat ke-i, pelipatgandaan berhenti setelah sekitar log₂ i langkah, dan menyisakan rentang kurang dari i tempat, yang dicakup pencarian biner dalam sekitar log₂ i lagi. Jadi pencarian ini butuh sekitar 2 log₂ i perbandingan, berapa pun panjang daftarnya. Jika target di dekat awal, ini mengalahkan pencarian biner, yang selalu butuh sekitar log₂ n. Jika di dekat akhir, pencarian eksponensial butuh hingga sekitar dua kali lipat. Untuk 40 nilai, aplikasi ini rata-rata butuh sekitar 3 perbandingan untuk lima tempat pertama dan sekitar 9 untuk lima tempat terakhir, dibandingkan sekitar 4,6 untuk pencarian biner.
Panjang tak diketahui, dan galloping
Jon Bentley dan Andrew Yao menjelaskan strategi pelipatgandaan ini pada tahun 1976 untuk pencarian tak terbatas: menemukan nilai dalam barisan terurut tanpa ujung yang diketahui, seperti daftar tak hingga atau stream yang hanya bisa Anda periksa di tempat tertentu. Ide yang sama mempercepat penggabungan. Saat salah satu dari dua run terurut terus menang, Timsort beralih ke galloping: ia melihat 1, 2, 4, 8 tempat ke depan di run lainnya untuk menemukan letak nilai berikutnya, alih-alih maju satu tempat setiap kali.
Jelajahi
Buka aplikasinya, pilih nilai di Cari, lalu tekan Langkah. Setiap kali tempat 1, 2, 4, 8, dan seterusnya dilihat, tempat itu disorot; begitu ada nilai yang tidak lebih kecil, rentang di antara dua tempat terakhir diarsir dan pencarian biner mengambil alih. Cari nilai kecil lalu nilai besar, dan bandingkan jumlahnya dengan kotak pencarian biner.
Pertanyaan yang sering diajukan
Berapa kompleksitas waktu pencarian eksponensial?
O(log i) untuk target di tempat ke-i, jadi paling banyak O(log n) untuk daftar berisi n nilai. Ia butuh memori tambahan O(1) dan daftar terurut.
Apa bedanya pencarian eksponensial dan pencarian biner?
Pencarian biner dimulai dari seluruh daftar dan perlu tahu panjangnya. Pencarian eksponensial lebih dulu menemukan rentang yang memuat target dengan melipatgandakan, lalu menjalankan pencarian biner hanya pada rentang itu. Ia lebih cepat jika target di dekat awal dan bekerja tanpa tahu panjang daftar.
Mengapa langkahnya dilipatgandakan, bukan ditambah jumlah tetap?
Menambah langkah tetap adalah pencarian lompat, yang perlu melihat sekitar n dibagi langkah kali untuk melintasi daftar. Pelipatgandaan mencapai tempat ke-i dalam sekitar log₂ i kali melihat, dan rentang yang disisakannya tidak pernah lebih dari dua kali ukuran yang perlu, jadi pencarian biner sesudahnya tetap singkat.
Di mana pencarian eksponensial digunakan?
Untuk mencari dalam data terurut yang tak terbatas atau sangat panjang, menggabungkan run terurut (galloping di Timsort), dan menemukan tempat pertama suatu kondisi menjadi benar saat batas atasnya tidak diketahui.
Siap mencobanya?
Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.
Coba pencarian eksponensial