Binær søgning
Binær søgning er sådan, man slår et ord op i en ordbog: åbn den på midten, se om ordet kommer før eller efter, og gentag med den halvdel. I en sorteret liste finder den enhver værdi blandt en million på højst 20 sammenligninger.
Idéen
I en sorteret liste fortæller én sammenligning dig mere end, om du har fundet den søgte værdi: den fortæller, hvilken side værdien er på. Sammenlign den søgte værdi med værdien i midten. Er de ens, er du færdig. Er den midterste værdi mindre, er alt før den også mindre, så den søgte værdi kan kun ligge efter den. Er den større, kan den søgte værdi kun ligge før den. Behold kun den halvdel, og gentag.
Et eksempel
Søg efter 23 i 2, 5, 8, 12, 16, 23, 38, 56, 72, 91. Den midterste værdi er 16, som er mindre, så kun 23 til 91 er tilbage. Deres midte er 56, som er større, så kun 23 og 38 er tilbage. Deres midte er 23: fundet på plads 6 efter 3 sammenligninger, hvor lineær søgning skal bruge 6. Søger man i samme liste efter 40, sammenlignes 16, 56, 23 og 38, og derefter er der intet tilbage: 4 sammenligninger for at vide, at 40 mangler, mod 10 med lineær søgning.
Halvering går hurtigt
Efter én sammenligning er højst halvdelen af listen tilbage, efter to en fjerdedel, efter k højst omkring n/2ᵏ. Søgningen stopper, når der intet er tilbage, så den kræver højst ⌊log₂ n⌋ + 1 sammenligninger: 6 for 40 værdier, 10 for 1.000, 20 for en million og 30 for en milliard. En dobbelt så lang liste giver kun én sammenligning mere. Det skrives O(log n).
Let at beskrive, svær at få rigtig
John Mauchly beskrev binær søgning i 1946, men ifølge Donald Knuth blev den første version, der virkede for alle listelængder, først udgivet i 1962. Jon Bentley fandt senere ud af, at kun omkring én ud af ti professionelle programmører skrev den korrekt: slutbetingelserne og plus eller minus én, når halvdelene skæres, er nemme at få galt. I 2006 viste Joshua Bloch, at den almindelige måde at finde midten på, (low + high) / 2, kan give overløb (overflow) for meget lange lister, en fejl, der havde ligget i Java-biblioteket i årevis. Skriver man low + (high − low) / 2, som appen gør, undgår man den.
Varianter og anvendelser
Med dubletter finder binær søgning et af matchene; versioner, der fortsætter til venstre eller højre, finder det første eller sidste, eller den plads, hvor en manglende værdi skulle indsættes. Samme halveringsidé finder roden af en ligning (bisektion), den version, hvor en fejl først dukkede op (git bisect), og svaret på mange optimeringsopgaver. Binære søgetræer gemmer data, så hvert opslag følger den samme halveringsvej.
Udforsk det
Åbn appen, vælg en værdi i Søg efter, og tryk på Trin. Det skraverede område er, hvor den søgte værdi stadig kan være; den midterste værdi er fremhævet, og den halvdel, der udelukkes, tones ned. Felterne viser, hvor mange værdier der stadig er mulige, og hvor mange sammenligninger en lineær søgning ville kræve for den samme værdi. Søg efter en værdi, der mangler, eller brug 40 søjler, for at se forskellen vokse.
Ofte stillede spørgsmål
Hvad er tidskompleksiteten af binær søgning?
O(log n): højst ⌊log₂ n⌋ + 1 sammenligninger for n værdier. I bedste fald er det én sammenligning, når den søgte værdi står i midten. Den iterative version kræver O(1) ekstra hukommelse.
Hvad er forskellen på binær søgning og lineær søgning?
Lineær søgning tjekker hver værdi efter tur og virker på enhver liste, men kan kræve n sammenligninger. Binær søgning virker kun på en sorteret liste, men udelukker halvdelen af det, der er tilbage, ved hver sammenligning, så den kræver omkring log₂ n.
Kan det betale sig at sortere en liste bare for at bruge binær søgning?
Kun hvis du søger i den mange gange. Sortering tager omkring n log n trin, mere end en enkelt lineær søgning. Når listen først er sorteret, er hver søgning derefter meget billig.
Kan binær søgning bruges på andet end lister?
Ja, på alt, hvor en test fortæller dig, hvilken side af svaret du er på: et interval af tal, versionerne af et program eller gættene i en højere-lavere-leg.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Prøv binær søgning