Încercări
Încă posibile
Necesar la căutarea binară

  • Valoarea căutată
  • Încă posibile
  • Comparate
  • Excluse
  • Găsite

Mai multe despre căutarea prin interpolare

Căutarea prin interpolare

Căutarea prin interpolare caută o valoare într-o listă sortată așa cum deschideți o carte de telefon: pentru un nume care începe cu T deschideți spre final, nu la mijloc. Estimează poziția valorii căutate din valorile de la ambele capete ale părții rămase. Alegeți valoarea și distribuția valorilor, parcurgeți încercările pas cu pas și vedeți când estimarea întrece căutarea binară și când nu. Apăsați Redare pentru a urmări căutarea sau Pas și Înapoi pentru a avansa câte un pas. Trageți glisorul pentru pași ca să săriți oriunde. Linia întreruptă marchează valoarea căutată, iar partea umbrită arată unde mai poate fi. Căutarea prin interpolare are nevoie de o listă sortată, așa că o listă nesortată este sortată mai întâi. Alegeți valoarea, cum sunt distribuite valorile, câte bare sunt sau introduceți propriile numere. Cu tabla selectată, săgețile avansează câte un pas, bara de spațiu pornește și pune pauză, iar Home și End sar la început și la sfârșit.

Cum funcționează

  1. Alegeți valoarea de căutat, cum sunt distribuite valorile și câte bare sunt. Sau introduceți propriile numere: căutarea prin interpolare le sortează mai întâi.
  2. Apăsați Redare sau folosiți Pas și Înapoi ca să avansați câte un pas. Trageți glisorul pentru pași ca să săriți oriunde în căutare.
  3. Comutați Distribuție între Uniformă, Goluri aleatorii și Asimetrică și comparați Încercări cu Necesar la căutarea binară.

Cum funcționează căutarea prin interpolare

Priviți prima și ultima valoare a părții din lista sortată care mai poate conține valoarea căutată. Dacă valoarea căutată se află, să zicem, la 40% din drumul de la prima valoare la ultima, verificați poziția aflată la 40% din lungime. Dacă acolo este valoarea căutată, ați terminat. Dacă e mai mică, rămân doar pozițiile de după ea; dacă e mai mare, doar cele dinaintea ei. Estimați din nou în ce a rămas. Dacă valoarea căutată e mai mică decât prima valoare sau mai mare decât ultima, nu se află în listă.

Când funcționează estimarea

Dacă valorile sunt distribuite uniform, ca 10, 20, 30 și așa mai departe, prima estimare nimerește valoarea căutată sau ajunge foarte aproape, iar căutarea are nevoie în medie de aproximativ log₂(log₂ n) încercări: cam 5 pentru un miliard de valori, față de 30 la căutarea binară. Dacă valorile se adună grămadă, ca 1, 2, 3, 4, 1000, estimările ajung mereu în locul greșit și fiecare încercare poate elimina o singură valoare, așa că în cel mai rău caz sunt n încercări. Căutarea binară nu se descurcă niciodată mai rău de aproximativ log₂ n.

Întrebări frecvente

Cum funcționează căutarea prin interpolare?

Într-o listă sortată estimează unde ar trebui să fie valoarea căutată din prima și ultima valoare a părții rămase, verifică acea poziție și păstrează doar partea din direcția corectă. Seamănă cu căutarea binară, dar cu o ghicire mai inteligentă decât mijlocul.

Este căutarea prin interpolare mai rapidă decât căutarea binară?

La valori distribuite uniform, da: în medie aproximativ log₂(log₂ n) încercări în loc de aproximativ log₂ n. La valori distribuite neuniform poate fi mult mai lentă, până la n încercări, în timp ce căutarea binară nu are niciodată nevoie de mai mult de aproximativ log₂ n.

De ce poate fi lentă?

Pentru că estimarea presupune că valorile cresc uniform. Dacă majoritatea valorilor sunt mici și câteva sunt uriașe, estimarea pentru o valoare căutată mică ajunge iar și iar lângă început și elimină de fiecare dată doar una sau două valori.

Unde se folosește căutarea prin interpolare?

Acolo unde cheile sunt distribuite aproape uniform și încercările sunt costisitoare, de exemplu la căutarea înregistrărilor pe disc după ID numeric sau hash. Multe sisteme o combină cu căutarea binară ca să păstreze un cel mai rău caz bun.

Numerele mele sunt trimise undeva?

Nu. Căutarea rulează în browserul dumneavoastră, iar ultimele setări rămân în stocarea locală a acestui browser.

Ești gata să încerci?

Deschide PictorX în browser – fără instalare și fără card de credit.

Mergi la editor