Căutarea prin interpolare

Când căutați „Taylor” într-o carte de telefon, nu o deschideți la mijloc: o deschideți spre final, pentru că T vine târziu în alfabet. Căutarea prin interpolare face același lucru cu numere. Ghicește unde ar trebui să fie valoarea căutată după cât de mare este, iar pe date distribuite uniform ghicirea este remarcabil de bună.

Un rând sortat de bare cu o linie de la prima la ultima bară și încercarea plasată acolo unde înălțimea valorii căutate întâlnește linia
Un rând sortat de bare cu o linie de la prima la ultima bară și încercarea plasată acolo unde înălțimea valorii căutate întâlnește linia

Ideea

Căutarea binară verifică mereu mijlocul, indiferent ce caută. Căutarea prin interpolare folosește valorile. Dacă partea rămasă din listă merge de la 10 la 100 și valoarea căutată este 70, aceasta se află la două treimi din drumul de la prima valoare la ultima, așa că încercarea se face la două treimi din lungime. Ca formulă, încercarea este la lo + (target − a[lo]) / (a[hi] − a[lo]) × (hi − lo). După încercare se păstrează partea din direcția corectă, exact ca la căutarea binară, și se estimează din nou.

Două exemple

În 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, căutarea lui 70 verifică imediat poziția 7: găsit din 1 încercare, unde căutarea binară are nevoie de 4. Acum luați 1, 2, 3, 4, 5, 6, 7, 8, 9, 999 și căutați 9. Din cauza lui 999, fiecare estimare ajunge lângă început: căutarea verifică 1, 2, 3 și așa mai departe, câte o poziție, și are nevoie de 9 încercări, unde căutarea binară are nevoie de 3.

Cât de rapidă este

Când valorile sunt distribuite uniform sau extrase aleatoriu dintr-o distribuție uniformă, fiecare încercare micșorează partea rămasă de la aproximativ n la aproximativ √n. Asta înseamnă în medie aproximativ log₂(log₂ n) încercări: cam 5 chiar și pentru un miliard de valori, față de 30 la căutarea binară. Când valorile sunt distribuite foarte neuniform, o încercare poate elimina o singură valoare, iar cel mai rău caz este de n încercări, la fel de rău ca la căutarea liniară. Fiecare încercare costă și o împărțire, așa că în practică merită mai ales când încercările sunt costisitoare, de exemplu citirile de pe disc.

Istorie și variante

W. W. Peterson a descris căutarea prin interpolare în 1957, pentru găsirea înregistrărilor în memorii cu acces aleatoriu. Media de log log n pentru chei distribuite uniform a fost demonstrată în 1978 de Perl, Itai și Avni. Versiunile practice se protejează de datele nepotrivite amestecând pași binari, de exemplu căutarea interpolare-secvențială sau căutarea interpolare-binară, astfel încât cel mai rău caz să rămână aproape de log n.

Explorați

Deschideți aplicația, alegeți o valoare în Valoare de căutat și apăsați Pas. Fiecare încercare spune cât de departe se află valoarea căutată între cele două valori de la capete și spre ce poziție indică asta. Setați Distribuție pe Uniformă și majoritatea căutărilor se termină dintr-o încercare; setați-o pe Asimetrică și încercările se târăsc de-a lungul începutului listei. Ultima casetă arată de câți pași ar avea nevoie căutarea binară pentru aceeași valoare.

Întrebări frecvente

Care este complexitatea în timp a căutării prin interpolare?

O(log log n) în medie pentru valori distribuite uniform și O(n) în cel mai rău caz. Are nevoie de O(1) memorie suplimentară și de o listă sortată.

Care este diferența dintre căutarea prin interpolare și căutarea binară?

Căutarea binară verifică mereu mijlocul a ceea ce a rămas. Căutarea prin interpolare verifică acolo unde ar trebui să fie valoarea căutată, judecând după valorile de la ambele capete. Asta e mult mai bine la valori distribuite uniform și poate fi mult mai rău la cele asimetrice.

Ce fel de date se potrivesc căutării prin interpolare?

Chei numerice sortate, distribuite destul de uniform: ID-uri consecutive cu puține goluri, marcaje de timp ale unor evenimente regulate sau chei hash. Se potrivește datelor la care o încercare este costisitoare, iar puțină aritmetică este ieftină.

De ce oferă aplicația distribuții diferite?

Pentru că distribuția decide cât de bune sunt estimările. Valorile uniforme fac căutarea prin interpolare să pară aproape magică, iar cele asimetrice îi arată slăbiciunea. Compararea lor cu numărul de la căutarea binară este cel mai clar mod de a vedea când să folosiți fiecare metodă.

Ești gata să încerci?

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

Încercați căutarea prin interpolare