- Target
- Masih mungkin
- Dibandingkan
- Tersisih
- Ditemukan
Pencarian eksponensial
Pencarian eksponensial menemukan nilai dalam daftar terurut dalam dua tahap. Pertama, ia melihat tempat 1, 2, 4, 8, 16, dan seterusnya, berlipat dua setiap kali, sampai nilai di sana tidak lebih kecil dari target. Lalu ia menjalankan pencarian biner pada rentang di antara dua tempat terakhir. Pilih nilai yang dicari dan lihat mengapa target di dekat awal ditemukan hanya dengan beberapa perbandingan. Tekan Putar untuk melihat pencarian, atau Langkah dan Mundur untuk maju satu langkah setiap kali. Geser penggeser langkah untuk melompat ke mana saja. Garis putus-putus menandai nilai yang dicari, dan bagian yang diarsir adalah tempat nilai itu masih mungkin berada. Pencarian eksponensial membutuhkan daftar terurut, jadi daftar yang belum terurut diurutkan dulu. Pilih nilainya, jumlah batang, atau ketik angka sendiri. Saat papan dipilih, tombol panah melangkah, spasi memutar dan menjeda, serta Home dan End melompat ke awal dan akhir.
Cara kerjanya
- Pilih nilai yang dicari dan jumlah batang. Atau ketik angka sendiri: pencarian eksponensial mengurutkannya dulu.
- Tekan Putar, atau gunakan Langkah dan Mundur untuk maju satu langkah setiap kali. Geser penggeser langkah untuk melompat ke mana saja dalam pencarian.
- Cari nilai di dekat awal dan satu lagi di dekat akhir, lalu bandingkan jumlahnya dengan Pencarian biner perlu.
Cara kerja pencarian eksponensial
Lihat nilai di tempat 1. Jika lebih kecil dari target, lihat tempat 2, lalu 4, 8, 16, berlipat dua setiap kali. Begitu ada nilai yang tidak lebih kecil, berhenti: target hanya bisa ada setelah tempat yang dilihat sebelumnya dan sebelum tempat ini. Jalankan pencarian biner pada rentang itu. Jika pelipatgandaan melewati akhir daftar, jalankan pencarian biner dari tempat terakhir yang dilihat sampai akhir.
Cepat di dekat awal, tanpa perlu tahu panjangnya
Untuk mencapai target di tempat ke-i, pelipatgandaan butuh sekitar log₂ i kali melihat, dan rentang yang ditemukannya berisi kurang dari i nilai, jadi pencarian biner butuh sekitar log₂ i lagi. Totalnya sekitar 2 log₂ i, yang bergantung pada letak target, bukan pada panjang daftar. Target di dekat awal ditemukan lebih cepat daripada dengan pencarian biner biasa; target di dekat akhir bisa butuh hingga sekitar dua kali lipat. Karena tidak pernah butuh panjang daftar, cara ini juga bekerja pada daftar yang terlalu panjang untuk diukur atau tidak diketahui ujungnya.
Pertanyaan yang sering diajukan
Bagaimana cara kerja pencarian eksponensial?
Pada daftar terurut, ia memeriksa tempat 1, 2, 4, 8, dan seterusnya sampai nilai di sana tidak lebih kecil dari target. Target lalu hanya bisa ada di antara dua tempat terakhir yang diperiksa, dan pencarian biner pada rentang itu menemukannya.
Apakah pencarian eksponensial lebih cepat daripada pencarian biner?
Jika target di dekat awal daftar, ya: target di tempat ke-i butuh sekitar 2 log₂ i perbandingan, berapa pun panjang daftarnya. Jika target di dekat akhir, pencarian biner biasa lebih cepat, hingga sekitar dua kali lipat.
Untuk apa pencarian ini digunakan?
Mencari dalam daftar yang panjangnya tidak diketahui atau tak terbatas, seperti stream atau barisan tak hingga, dan menggabungkan run terurut, yang kecocokan berikutnya biasanya dekat. Mode galloping Timsort memakai ide pelipatgandaan yang sama.
Mengapa disebut eksponensial?
Karena tempat yang diperiksanya tumbuh secara eksponensial: 1, 2, 4, 8, 16, masing-masing dua kali yang sebelumnya. Ia juga disebut doubling search atau galloping search.
Apakah angka saya dikirim ke mana pun?
Tidak. Pencarian berjalan di browser Anda, dan pengaturan terakhir Anda tersimpan di penyimpanan lokal browser ini.
Siap mencobanya?
Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.
Ke Editor