Exponentiell sökning

Binärsökning måste veta var listan slutar innan den kan titta i mitten. Det behöver inte exponentiell sökning: den galopperar framåt i allt större steg tills den skjuter förbi målet, och binärsöker sedan det sista steget. Det gör den idealisk för listor med okänd längd och snabb för värden nära början.

En sorterad rad staplar med hopp av dubblerad längd över plats 1, 2, 4 och 8, och sträckan mellan de två sista hoppen skuggad
En sorterad rad staplar med hopp av dubblerad längd över plats 1, 2, 4 och 8, och sträckan mellan de två sista hoppen skuggad

Idén

Kontrollera värdet på plats 1, sedan 2, 4, 8, 16 och så vidare, varje plats dubbelt så långt fram som den förra. Så länge värdet där är mindre än målet måste målet ligga längre fram. Första gången ett värde inte är mindre är målet instängt: det ligger efter den förra kontrollerade platsen och inte senare än den här. Den sträckan är sorterad, så en binärsökning hittar målet eller visar att det saknas.

Ett exempel

Sök efter 23 i 2, 5, 8, 12, 16, 23, 38, 56, 72, 91. Plats 1 har 2, plats 2 har 5, plats 4 har 12, alla mindre. Plats 8 har 56, som är större, så 23 kan bara finnas på plats 5 till 7. Binärsökningen kontrollerar mitten av dem, plats 6, och hittar 23: 5 jämförelser, där vanlig binärsökning behöver 3. Söker du efter 12 i samma lista stannar den på plats 4 efter 3 jämförelser, en färre än binärsökning, och 2 hittas på plats 1 med en enda jämförelse.

Hur många jämförelser

För ett mål på plats i stannar dubbleringen efter ungefär log₂ i steg, och den lämnar en sträcka på färre än i platser, som binärsökning täcker med ungefär log₂ i till. Så sökningen kostar ungefär 2 log₂ i jämförelser, oavsett listans längd. När målet är nära början slår det binärsökning, som alltid kostar ungefär log₂ n. När det är nära slutet kostar exponentiell sökning upp till ungefär dubbelt så mycket. För 40 värden ger appen i snitt ungefär 3 jämförelser för de fem första platserna och ungefär 9 för de fem sista, mot ungefär 4,6 för binärsökning.

Okänd längd, och galloping

Jon Bentley och Andrew Yao beskrev den här dubbleringsstrategin 1976 för obegränsad sökning: att hitta ett värde i en sorterad följd utan känt slut, som en oändlig lista eller en dataström som du bara kan fråga plats för plats. Samma idé snabbar upp sammanslagning. När den ena av två sorterade sekvenser fortsätter att vinna byter Timsort till galloping: den tittar 1, 2, 4, 8 platser framåt i den andra sekvensen för att hitta var nästa värde hör hemma, i stället för att gå en plats i taget.

Utforska den

Öppna appen, välj ett värde i Sök efter och tryck på Steg. Varje kontroll av plats 1, 2, 4, 8 och så vidare markeras; så fort ett värde inte är mindre skuggas sträckan mellan de två sista platserna och binärsökningen tar över. Sök efter ett litet värde och sedan ett stort, och jämför antalet med rutan för binärsökning.

Ofta ställda frågor

Vilken tidskomplexitet har exponentiell sökning?

O(log i) för ett mål på plats i, alltså högst O(log n) för en lista med n värden. Den behöver O(1) extra minne och en sorterad lista.

Vad är skillnaden mellan exponentiell sökning och binärsökning?

Binärsökning börjar med hela listan och behöver dess längd. Exponentiell sökning hittar först genom dubblering en sträcka som innehåller målet och binärsöker sedan bara den sträckan. Den är snabbare när målet är nära början och fungerar utan att känna till längden.

Varför dubbla steget och inte lägga till ett fast antal?

Att lägga till ett fast steg är hoppsökning (jump search), som behöver ungefär n delat med steget kontroller för att ta sig genom listan. Dubblering når plats i med ungefär log₂ i kontroller, och sträckan den lämnar är aldrig mer än dubbelt så stor som nödvändigt, så binärsökningen efteråt förblir kort.

Var används exponentiell sökning?

Vid sökning i obegränsade eller mycket långa sorterade data, vid sammanslagning av sorterade sekvenser (galloping i Timsort) och för att hitta den första plats där ett villkor blir sant när ingen övre gräns är känd.

Redo att prova det?

Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.

Prova exponentiell sökning