Pencarian interpolasi

Saat mencari "Taylor" di buku telepon, Anda tidak membukanya di tengah: Anda membukanya dekat bagian belakang, karena T ada di bagian akhir alfabet. Pencarian interpolasi melakukan hal yang sama dengan angka. Ia menebak letak target dari besarnya, dan pada data yang tersebar merata tebakan itu sangat jitu.

Deretan batang terurut dengan garis dari batang pertama ke batang terakhir, dan pemeriksaan di tempat tinggi target bertemu garis itu
Deretan batang terurut dengan garis dari batang pertama ke batang terakhir, dan pemeriksaan di tempat tinggi target bertemu garis itu

Idenya

Pencarian biner selalu memeriksa bagian tengah, apa pun yang dicari. Pencarian interpolasi memakai nilainya. Jika bagian daftar yang tersisa berkisar dari 10 sampai 100 dan targetnya 70, target berada di dua pertiga jarak dari nilai pertama ke nilai terakhir, jadi ia memeriksa tempat di dua pertiga panjangnya. Dalam bentuk rumus, tempat pemeriksaan adalah lo + (target − a[lo]) / (a[hi] − a[lo]) × (hi − lo). Setelah memeriksa, ia menyimpan bagian di sisi yang benar, persis seperti pencarian biner, lalu memperkirakan lagi.

Dua contoh

Pada 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, mencari 70 langsung memeriksa tempat ke-7: ditemukan dalam 1 pemeriksaan, sedangkan pencarian biner perlu 4. Sekarang ambil 1, 2, 3, 4, 5, 6, 7, 8, 9, 999 dan cari 9. Karena ada 999, setiap perkiraan jatuh di dekat awal: pencarian memeriksa tempat 1, 2, 3, dan seterusnya, satu tempat setiap kali, dan perlu 9 pemeriksaan, sedangkan pencarian biner perlu 3.

Seberapa cepat

Jika nilai tersebar merata, atau diambil acak dari distribusi seragam, setiap pemeriksaan menyusutkan bagian yang tersisa dari sekitar n menjadi sekitar √n. Hasilnya rata-rata sekitar log₂(log₂ n) pemeriksaan: sekitar 5 bahkan untuk satu miliar nilai, dibandingkan 30 untuk pencarian biner. Jika nilai tersebar sangat tidak merata, satu pemeriksaan bisa menyingkirkan hanya satu nilai, dan kasus terburuknya n pemeriksaan, seburuk pencarian linear. Setiap pemeriksaan juga memerlukan pembagian, jadi dalam praktik cara ini terutama menguntungkan saat pemeriksaan mahal, misalnya pembacaan dari disk.

Sejarah dan varian

W. W. Peterson menjelaskan pencarian interpolasi pada 1957, untuk mencari catatan di penyimpanan akses acak. Rata-rata log log n untuk kunci yang tersebar merata dibuktikan pada 1978 oleh Perl, Itai, dan Avni. Versi praktis melindungi diri dari data buruk dengan menyelipkan langkah biner, misalnya pencarian interpolasi-sekuensial atau pencarian interpolasi-biner, sehingga kasus terburuknya tetap dekat log n.

Jelajahi

Buka aplikasinya, pilih nilai di Cari, dan tekan Langkah. Setiap pemeriksaan menjelaskan seberapa jauh target berada di antara kedua nilai ujung dan tempat mana yang ditunjuknya. Ubah Sebaran ke Merata dan sebagian besar pencarian selesai dalam satu pemeriksaan; ubah ke Timpang dan pemeriksaan merayap di awal daftar. Kotak terakhir menunjukkan berapa langkah yang dibutuhkan pencarian biner untuk nilai yang sama.

Pertanyaan yang sering diajukan

Berapa kompleksitas waktu pencarian interpolasi?

O(log log n) rata-rata untuk nilai yang tersebar merata, dan O(n) dalam kasus terburuk. Ia memerlukan memori tambahan O(1) dan daftar terurut.

Apa perbedaan pencarian interpolasi dan pencarian biner?

Pencarian biner selalu memeriksa bagian tengah dari yang tersisa. Pencarian interpolasi memeriksa tempat target seharusnya berada, berdasarkan nilai di kedua ujung. Itu jauh lebih baik pada nilai yang tersebar merata dan bisa jauh lebih buruk pada nilai yang timpang.

Data seperti apa yang cocok untuk pencarian interpolasi?

Kunci numerik terurut yang tersebar cukup merata: ID berurutan dengan sedikit celah, stempel waktu peristiwa yang teratur, atau kunci hasil hash. Cocok untuk data yang pemeriksaannya mahal sementara sedikit hitungan itu murah.

Mengapa aplikasi ini menawarkan sebaran yang berbeda?

Karena sebaran menentukan seberapa baik perkiraannya. Nilai yang merata membuat pencarian interpolasi tampak hampir ajaib, dan nilai yang timpang menunjukkan kelemahannya. Membandingkannya dengan jumlah langkah pencarian biner adalah cara paling jelas untuk melihat kapan memakai yang mana.

Siap mencobanya?

Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.

Coba pencarian interpolasi