Pencarian lompat
Pencarian lompat mirip cara mencari halaman di buku tanpa daftar isi: balik maju beberapa halaman sekaligus sambil melirik nomor halaman, dan begitu terlewat, telusuri mundur bagian terakhir itu. Pada daftar terurut, cara ini butuh jauh lebih sedikit perbandingan daripada memeriksa setiap nilai.
Idenya
Dalam daftar terurut, nilai terakhir suatu blok memberi tahu apakah target mungkin ada di blok itu: jika lebih kecil dari target, setiap nilai dalam blok juga lebih kecil. Jadi tidak perlu melihat ke dalamnya. Periksa nilai terakhir tiap blok secara bergantian, lewati seluruh blok, sampai ada yang tidak lebih kecil dari target. Maka target hanya mungkin ada di blok itu: pindai dari awalnya.
Contoh
Cari 23 dalam 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 dengan blok berisi 3. Blok pertama diakhiri 8, yang lebih kecil, jadi lewati. Blok kedua diakhiri 23, yang tidak lebih kecil, jadi 23 hanya mungkin ada di 12, 16, 23. Memindainya memberi 12, 16, lalu 23: ditemukan setelah 5 perbandingan, sedangkan pencarian linear perlu 6 dan pencarian biner 3. Saat mencari 40, akhir blok 8, 23, dan 72 mengarah ke blok 38, 56, 72; 38 lebih kecil dan 56 sudah lebih besar, jadi 40 tidak ada di sana: 5 perbandingan lagi.
Mengapa √n
Dengan blok berisi m nilai, menemukan blok yang tepat butuh paling banyak sekitar n/m perbandingan dan memindainya paling banyak m. Lompatan yang sedikit dan jauh membuat pemindaian panjang; lompatan yang banyak dan pendek membuat pelompatan panjang. Jumlah n/m + m paling kecil saat kedua bagian sama, pada m = √n, yaitu sekitar 2√n. Untuk 40 nilai, itu berarti blok berisi 6 dan paling banyak 13 perbandingan; untuk sejuta nilai, blok berisi 1.000 dan sekitar 2.000 perbandingan.
Kapan cocok dipakai
Pencarian biner butuh lebih sedikit perbandingan, sekitar log₂ n. Tetapi pencarian biner melompat maju-mundur di seluruh daftar, sedangkan pencarian lompat hanya bergerak maju dan mundur sekali, ke awal satu blok. Karena itu, ia menarik untuk data di pita atau dalam struktur bertaut yang lambat untuk mundur. Ben Shneiderman menjelaskannya sebagai jump searching pada 1978. Ide yang sama untuk membagi menjadi √n blok, yang sering disebut dekomposisi akar kuadrat, muncul di banyak algoritma lain.
Jelajahi
Buka aplikasinya, pilih nilai di Cari, lalu tekan Langkah. Setiap lompatan menyorot nilai terakhir suatu blok; blok yang dilewati memudar, dan blok yang bisa memuat target diarsir selama dipindai. Ubah Ukuran lompatan dari √n ke 2 atau 8 dengan 40 batang dan lihat keseimbangan antara lompatan dan pemindaian bergeser.
Pertanyaan yang sering diajukan
Apa kompleksitas waktu pencarian lompat?
O(√n) dengan blok berisi √n nilai: paling banyak sekitar 2√n perbandingan. Ia butuh memori tambahan O(1) dan daftar terurut.
Apa beda pencarian lompat dan pencarian biner?
Pencarian biner membagi dua bagian yang tersisa setiap kali dan butuh sekitar log₂ n perbandingan, tetapi bergerak maju-mundur. Pencarian lompat melompat maju dengan langkah tetap dan memindai satu blok, butuh sekitar 2√n perbandingan, dan hanya mundur sekali.
Bisakah pemindaian di blok terakhir memakai pencarian biner?
Bisa. Mencari di blok dengan pencarian biner memangkas pemindaian dari m perbandingan menjadi sekitar log₂ m. Lompatannya tetap butuh n/m, jadi blok yang lebih besar jadi lebih menguntungkan.
Apakah pencarian lompat membutuhkan daftar terurut?
Ya. Melewati blok hanya aman karena nilai terakhirnya yang lebih kecil berarti setiap nilai di dalamnya juga lebih kecil. Aplikasi ini mengurutkan daftar yang belum terurut terlebih dulu.
Siap mencobanya?
Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.
Coba pencarian lompat