Pemeriksaan
Masih mungkin
Pencarian biner perlu

  • Target
  • Masih mungkin
  • Dibandingkan
  • Tersisih
  • Ditemukan

Info lebih lanjut tentang pencarian interpolasi

Pencarian interpolasi

Pencarian interpolasi mencari nilai dalam daftar terurut seperti saat Anda membuka buku telepon: untuk nama berawalan T, Anda membuka dekat bagian belakang, bukan di tengah. Ia memperkirakan tempat target dari nilai di kedua ujung bagian yang tersisa. Pilih nilai dan sebaran nilai, telusuri pemeriksaan satu per satu, dan lihat kapan perkiraannya mengalahkan pencarian biner dan kapan tidak. 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 berarsir adalah tempat nilai itu masih mungkin berada. Pencarian interpolasi membutuhkan daftar terurut, jadi daftar yang belum terurut diurutkan dulu. Pilih nilainya, sebaran nilai, 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

  1. Pilih nilai yang dicari, sebaran nilai, dan jumlah batang. Atau ketik angka sendiri: pencarian interpolasi mengurutkannya dulu.
  2. Tekan Putar, atau gunakan Langkah dan Mundur untuk maju satu langkah setiap kali. Geser penggeser langkah untuk melompat ke mana saja dalam pencarian.
  3. Ganti Sebaran antara Merata, Jarak acak, dan Timpang, lalu bandingkan Pemeriksaan dengan Pencarian biner perlu.

Cara kerja pencarian interpolasi

Lihat nilai pertama dan terakhir dari bagian daftar terurut yang masih bisa memuat target. Jika target berada, misalnya, di 40% jarak dari nilai pertama ke nilai terakhir, periksa tempat di 40% panjang bagian itu. Jika nilai di sana adalah target, selesai. Jika lebih kecil, hanya tempat setelahnya yang tersisa; jika lebih besar, hanya tempat sebelumnya. Perkirakan lagi di bagian yang tersisa. Jika target lebih kecil dari nilai pertama atau lebih besar dari nilai terakhir, target tidak ada di sana.

Kapan perkiraannya berhasil

Jika nilai tersebar merata, seperti 10, 20, 30, dan seterusnya, perkiraan pertama jatuh tepat pada target atau sangat dekat, dan rata-rata pencarian perlu sekitar log₂(log₂ n) pemeriksaan: sekitar 5 untuk satu miliar nilai, dibandingkan 30 untuk pencarian biner. Jika nilai menumpuk, seperti 1, 2, 3, 4, 1000, perkiraannya terus jatuh di tempat yang salah dan setiap pemeriksaan mungkin hanya menyingkirkan satu nilai, sehingga kasus terburuknya n pemeriksaan. Pencarian biner tidak pernah lebih buruk dari sekitar log₂ n.

Pertanyaan yang sering diajukan

Bagaimana cara kerja pencarian interpolasi?

Pada daftar terurut, ia memperkirakan letak target dari nilai pertama dan terakhir bagian yang tersisa, memeriksa tempat itu, dan hanya menyimpan bagian di sisi yang benar. Ini seperti pencarian biner dengan tebakan yang lebih cerdas daripada bagian tengah.

Apakah pencarian interpolasi lebih cepat dari pencarian biner?

Pada nilai yang tersebar merata, ya: rata-rata sekitar log₂(log₂ n) pemeriksaan, bukan sekitar log₂ n. Pada nilai yang tidak tersebar merata, ia bisa jauh lebih lambat, hingga n pemeriksaan, sedangkan pencarian biner tidak pernah perlu lebih dari sekitar log₂ n.

Mengapa bisa lambat?

Karena perkiraannya menganggap nilai naik secara merata. Jika sebagian besar nilai kecil dan beberapa sangat besar, perkiraan untuk target kecil berulang kali jatuh di dekat awal dan hanya menyingkirkan satu atau dua nilai setiap kali.

Di mana pencarian interpolasi digunakan?

Di tempat kunci tersebar hampir merata dan pemeriksaan mahal, misalnya mencari catatan berdasarkan ID numerik atau hash di disk. Banyak sistem menggabungkannya dengan pencarian biner agar kasus terburuknya tetap baik.

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