Binärsökning
Binärsökning är hur du slår upp ett ord i en ordbok: öppna den på mitten, se om ordet kommer före eller efter, och upprepa med den halvan. I en sorterad lista hittar den vilket värde som helst bland en miljon på högst 20 jämförelser.
Idén
I en sorterad lista säger en jämförelse mer än om du har hittat det sökta värdet: den säger vilken sida värdet ligger på. Jämför det sökta värdet med värdet i mitten. Är de lika är du klar. Är mittvärdet mindre är allt före det också mindre, så det sökta värdet kan bara komma efter. Är det större kan det sökta värdet bara komma före. Behåll bara den halvan och upprepa.
Ett exempel
Sök efter 23 i 2, 5, 8, 12, 16, 23, 38, 56, 72, 91. Mittvärdet är 16, som är mindre, så bara 23 till 91 återstår. Deras mitt är 56, som är större, så bara 23 och 38 återstår. Deras mitt är 23: hittat på plats 6 efter 3 jämförelser, där linjär sökning behöver 6. Söker man i samma lista efter 40 jämförs 16, 56, 23 och 38, och sedan finns inget kvar: 4 jämförelser för att veta att 40 saknas, mot 10 för linjär sökning.
Halveringar går fort
Efter en jämförelse är högst halva listan kvar, efter två en fjärdedel, efter k högst ungefär n/2ᵏ. Sökningen slutar när inget finns kvar, så den behöver högst ⌊log₂ n⌋ + 1 jämförelser: 6 för 40 värden, 10 för 1 000, 20 för en miljon och 30 för en miljard. En dubbelt så lång lista ger bara en jämförelse till. Det skrivs O(log n).
Lätt att beskriva, svår att få rätt
John Mauchly beskrev binärsökning 1946, men enligt Donald Knuth publicerades den första versionen som fungerade för alla listlängder inte förrän 1962. Jon Bentley fann senare att bara ungefär en av tio yrkesprogrammerare skrev den korrekt: slutvillkoren och plus eller minus ett när halvorna delas är lätta att få fel. 2006 visade Joshua Bloch att det vanliga sättet att hitta mitten, (low + high) / 2, kan ge spill (overflow) för mycket långa listor, en bugg som hade funnits i Javas bibliotek i flera år. Skriver man low + (high − low) / 2, som appen gör, undviker man den.
Varianter och användning
Med dubbletter hittar binärsökning en av träffarna; versioner som fortsätter åt vänster eller höger hittar den första eller sista, eller platsen där ett saknat värde skulle infogas. Samma halveringsidé hittar roten till en ekvation (bisektion), versionen där en bugg först dök upp (git bisect), och svaret på många optimeringsgåtor. Binära sökträd lagrar data så att varje uppslag följer samma halveringsväg.
Utforska den
Öppna appen, välj ett värde i Sök efter och tryck på Steg. Det skuggade området är där det sökta värdet fortfarande kan finnas; mittvärdet är markerat, och halvan som utesluts tonas ned. Rutorna visar hur många värden som fortfarande är möjliga och hur många jämförelser en linjär sökning skulle behöva för samma värde. Sök efter ett värde som saknas, eller använd 40 staplar, för att se skillnaden växa.
Ofta ställda frågor
Vilken tidskomplexitet har binärsökning?
O(log n): högst ⌊log₂ n⌋ + 1 jämförelser för n värden. I bästa fall räcker en jämförelse, när det sökta värdet står i mitten. Den iterativa versionen behöver O(1) extra minne.
Vad är skillnaden mellan binärsökning och linjär sökning?
Linjär sökning kontrollerar varje värde i tur och ordning och fungerar på alla listor, men kan behöva n jämförelser. Binärsökning fungerar bara på en sorterad lista, men utesluter hälften av det som är kvar vid varje jämförelse, så den behöver ungefär log₂ n.
Lönar det sig att sortera en lista bara för att använda binärsökning?
Bara om du söker i den många gånger. Sortering tar ungefär n log n steg, fler än en enda linjär sökning. När listan väl är sorterad är varje sökning efter det mycket billig.
Kan binärsökning användas på annat än listor?
Ja, på allt där ett test säger vilken sida av svaret du är på: ett intervall av tal, versionerna av ett program eller gissningarna i en högre-lägre-lek.
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Prova binärsökning