Binair zoeken

Vindt een waarde in een gesorteerde array door naar het midden te kijken en de helft weg te gooien waar hij niet kan zitten. Elke vergelijking halveert wat over is.

beste geval Ω(1)
gemiddeld Θ(log n)
slechtste geval O(log n)
geheugen O(1)

Wat betekent dit?

Gesorteerd: in oplopende volgorde. Binair zoeken heeft dit nodig; op ongesorteerde gegevens geeft het foute antwoorden.
Halveren: elke vergelijking gooit de helft van de rest weg, de helft waar het doel niet kan zitten.
log₂ n: hoe vaak je n kunt halveren tot er 1 over is. Voor 64 waarden is dat 6, dus hooguit 7 vergelijkingen.

midden (mid)
gevonden
uitgesloten
doel

0 / 14 stappen

Elk midden dat het zoeken zou kunnen kiezen; een run is één pad naar beneden. Niveaus: 5 = ⌈log₂(24 + 1)⌉, het maximale aantal vergelijkingen.

Snelheid 8 stappen / s

Spatie: afspelen of pauzeren. Pijltjes links/rechts: stap. Home en End: springen.

Probeer dit: Kies een doel dat niet in de array zit. Het zoeken stopt toch na hooguit ⌈log₂(n + 1)⌉ vergelijkingen, als lo voorbij hi schiet.

Hoe het werkt

Binair zoeken houdt twee markers, lo en hi, rond het deel van de array waar het doel nog kan zitten. Het kijkt naar de waarde in het midden: is dat het doel, dan klaar; is die kleiner, dan kan het doel alleen rechts liggen, dus lo schuift voorbij het midden; is die groter, dan schuift hi ervoor. Elke stap halveert de rest: 64 waarden kosten hooguit 7 vergelijkingen, een miljoen hooguit 20. Als lo voorbij hi schiet, is er niets meer over: de waarde zit niet in de array.

Wanneer het een goede keuze is

Gebruik binair zoeken zodra de gegevens gesorteerd zijn en je naar elke positie kunt springen: een woord in een gesorteerde lijst, een versie in een releasegeschiedenis, git bisect, de invoegplek in een gesorteerde array. Op ongesorteerde gegevens geeft het foute antwoorden, en eerst sorteren loont pas bij veel zoekopdrachten.