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)
- Θ(log n)
- slechtste geval O(log n)
- geheugen O(1)
log₂ n: hoe vaak je n kunt halveren tot er 1 over is. Voor 64 waarden is dat 6, dus hooguit 7 vergelijkingen.
Andere begrippen op deze pagina
- 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.
- midden (mid)
- gevonden
- uitgesloten
- doel
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.