Eksponentiel søgning

Binær søgning skal vide, hvor listen slutter, før den kan kigge i midten. Det skal eksponentiel søgning ikke: den galopperer fremad i stadig større skridt, indtil den skyder forbi målet, og søger derefter binært i det sidste skridt. Det gør den ideel til lister af ukendt længde og hurtig til værdier tæt på starten.

En sorteret række søjler med spring af fordoblet længde over plads 1, 2, 4 og 8, og stykket mellem de sidste to spring skraveret
En sorteret række søjler med spring af fordoblet længde over plads 1, 2, 4 og 8, og stykket mellem de sidste to spring skraveret

Idéen

Tjek værdien på plads 1, derefter 2, 4, 8, 16 og så videre, hver plads dobbelt så langt fremme som den forrige. Så længe værdien der er mindre end målet, må målet ligge længere fremme. Første gang en værdi ikke er mindre, er målet fanget: det ligger efter den forrige tjekkede plads og ikke senere end denne. Det stykke er sorteret, så en binær søgning finder målet eller viser, at det mangler.

Et eksempel

Søg efter 23 i 2, 5, 8, 12, 16, 23, 38, 56, 72, 91. Plads 1 rummer 2, plads 2 rummer 5, plads 4 rummer 12, alle mindre. Plads 8 rummer 56, som er større, så 23 kan kun stå på plads 5 til 7. Binær søgning tjekker midten af dem, plads 6, og finder 23: 5 sammenligninger, hvor almindelig binær søgning skal bruge 3. Søger du efter 12 i samme liste, stopper den på plads 4 efter 3 sammenligninger, én færre end binær søgning, og 2 findes på plads 1 med en enkelt sammenligning.

Hvor mange sammenligninger

For et mål på plads i stopper fordoblingen efter omkring log₂ i trin, og den efterlader et stykke på færre end i pladser, som binær søgning dækker med omkring log₂ i mere. Så søgningen koster omkring 2 log₂ i sammenligninger, uanset listens længde. Når målet er tæt på starten, slår det binær søgning, som altid betaler omkring log₂ n. Når det er tæt på slutningen, betaler eksponentiel søgning op til omkring dobbelt så meget. For 40 værdier giver appen i gennemsnit omkring 3 sammenligninger for de første fem pladser og omkring 9 for de sidste fem, mod omkring 4,6 for binær søgning.

Ukendt længde, og galloping

Jon Bentley og Andrew Yao beskrev denne fordoblingsstrategi i 1976 til ubegrænset søgning: at finde en værdi i en sorteret følge uden kendt slutning, som en uendelig liste eller en datastrøm, du kun kan slå op i plads for plads. Samme idé gør fletning hurtigere. Når den ene af to sorterede sekvenser bliver ved med at vinde, skifter Timsort til galloping: den kigger 1, 2, 4, 8 pladser frem i den anden sekvens for at finde, hvor den næste værdi skal hen, i stedet for at gå én plads ad gangen.

Udforsk den

Åbn appen, vælg en værdi i Søg efter, og tryk på Trin. Hvert kig på plads 1, 2, 4, 8 og så videre fremhæves; så snart en værdi ikke er mindre, skraveres stykket mellem de sidste to pladser, og binær søgning tager over. Søg efter en lille værdi og derefter en stor, og sammenlign antallet med feltet for binær søgning.

Ofte stillede spørgsmål

Hvad er tidskompleksiteten for eksponentiel søgning?

O(log i) for et mål på plads i, så højst O(log n) for en liste med n værdier. Den kræver O(1) ekstra hukommelse og en sorteret liste.

Hvad er forskellen på eksponentiel søgning og binær søgning?

Binær søgning starter med hele listen og kræver dens længde. Eksponentiel søgning finder først ved fordobling et stykke, der indeholder målet, og søger derefter kun binært i det stykke. Den er hurtigere, når målet er tæt på starten, og virker uden at kende længden.

Hvorfor fordoble skridtet og ikke lægge et fast tal til?

At lægge et fast skridt til er jump search, som kræver omkring n divideret med skridtet kig for at komme gennem listen. Fordobling når plads i med omkring log₂ i kig, og det stykke, den efterlader, er aldrig mere end dobbelt så stort som nødvendigt, så den efterfølgende binære søgning forbliver kort.

Hvor bruges eksponentiel søgning?

Til søgning i ubegrænsede eller meget lange sorterede data, til fletning af sorterede sekvenser (galloping i Timsort) og til at finde den første plads, hvor en betingelse bliver sand, når ingen øvre grænse kendes.

Er du klar til at prøve?

Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.

Prøv eksponentiel søgning