- Target
- Blok aktif
- Dibandingkan
- Tersisih
- Ditemukan
Pencarian lompat
Pencarian lompat berada di antara pencarian linear dan pencarian biner. Ia bergerak melalui daftar terurut dengan lompatan m tempat, hanya memeriksa nilai terakhir tiap blok, sampai tiba di blok yang nilai terakhirnya tidak lebih kecil dari target. Lalu ia memindai blok itu dari awal. Pilih nilai dan ukuran lompatan, lalu lihat berapa perbandingan yang dibutuhkan lompatan dan pemindaian. Tekan Putar untuk melihat pencarian, atau Langkah dan Mundur untuk maju satu perbandingan setiap kali. Geser penggeser langkah untuk melompat ke mana saja. Garis putus-putus menandai nilai yang dicari, dan bagian yang diarsir adalah blok aktif. Pencarian lompat membutuhkan daftar terurut, jadi daftar yang belum terurut diurutkan dulu. Pilih nilainya, ukuran lompatan, 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, ukuran lompatan, dan jumlah batang. Atau ketik angka sendiri: pencarian lompat mengurutkannya dulu.
- Tekan Putar, atau gunakan Langkah dan Mundur untuk maju satu perbandingan setiap kali. Geser penggeser langkah untuk melompat ke mana saja dalam pencarian.
- Coba ukuran lompatan 2 dan 8 pada 40 batang, lalu bandingkan jumlah perbandingannya dengan √n.
Cara kerja pencarian lompat
Bagi daftar terurut menjadi blok berisi m nilai. Lihat nilai terakhir blok pertama. Jika lebih kecil dari target, target tidak mungkin ada di mana pun dalam blok itu, jadi lompat ke akhir blok berikutnya dan lihat lagi. Begitu nilai terakhir suatu blok tidak lebih kecil, target hanya mungkin ada di blok itu: kembali ke awalnya dan periksa nilainya satu per satu sampai target ditemukan atau terlewati.
Memilih ukuran lompatan
Dengan n nilai, lompatan butuh paling banyak n/m perbandingan dan pemindaian paling banyak m. Lompatan kecil membuat pemindaian pendek tetapi lompatannya banyak; lompatan besar sebaliknya. Totalnya, n/m + m, paling kecil saat m = √n, yang memberi sekitar 2√n perbandingan: paling banyak 13 untuk 40 nilai, dibandingkan 40 untuk pencarian linear dan 6 untuk pencarian biner. Pencarian lompat tidak pernah mundur lebih dari satu blok, yang membantu saat bergerak mundur dalam data itu lambat.
Pertanyaan yang sering diajukan
Bagaimana cara kerja pencarian lompat?
Pada daftar terurut, ia melompat maju sejauh m tempat dan memeriksa nilai terakhir tiap blok. Saat nilai itu tidak lagi lebih kecil dari target, target hanya mungkin ada di blok itu, yang lalu dipindai dari awal.
Berapa ukuran lompatan terbaik?
√n, dibulatkan. Lompatan butuh paling banyak n/m perbandingan dan pemindaian paling banyak m, dan jumlahnya paling kecil saat keduanya sama, yaitu pada m = √n. Itu memberi sekitar 2√n perbandingan dalam kasus terburuk.
Apakah pencarian lompat lebih cepat daripada pencarian biner?
Tidak, pencarian biner butuh lebih sedikit perbandingan: sekitar log₂ n dibandingkan sekitar 2√n. Pencarian lompat tetap bisa unggul saat mundur dalam data itu mahal, karena ia hanya mundur sekali, ke awal satu blok.
Kecocokan mana yang ditemukan jika ada nilai yang berulang?
Yang pertama. Setiap blok yang dilewati diakhiri nilai yang lebih kecil dari target, jadi tidak ada blok sebelumnya yang bisa memuat kecocokan, dan pemindaian dimulai dari awal blok.
Apakah angka saya dikirim ke suatu tempat?
Tidak. Pencarian berjalan di browser Anda, dan pengaturan terakhir Anda disimpan di penyimpanan lokal browser ini.
Siap mencobanya?
Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.
Ke Editor