Binair zoeken
Binair zoeken is hoe je een woord opzoekt in een woordenboek: sla het in het midden open, kijk of het woord ervoor of erna komt, en herhaal dat met die helft. In een gesorteerde lijst vindt het elke waarde uit een miljoen in hoogstens 20 vergelijkingen.
Het idee
In een gesorteerde lijst vertelt één vergelijking je meer dan of je de gezochte waarde hebt gevonden: ze vertelt aan welke kant die staat. Vergelijk de gezochte waarde met de waarde in het midden. Zijn ze gelijk, dan ben je klaar. Is de middelste waarde kleiner, dan is alles ervoor ook kleiner, dus kan de gezochte waarde alleen erna komen. Is ze groter, dan kan die alleen ervoor komen. Houd alleen die helft over en herhaal.
Een voorbeeld
Zoek 23 in 2, 5, 8, 12, 16, 23, 38, 56, 72, 91. De middelste waarde is 16, die is kleiner, dus blijven alleen 23 tot 91 over. Hun midden is 56, die is groter, dus blijven alleen 23 en 38 over. Hun midden is 23: gevonden op plek 6 na 3 vergelijkingen, waar lineair zoeken er 6 nodig heeft. Zoek je in dezelfde lijst naar 40, dan vergelijk je 16, 56, 23 en 38, en daarna is er niets meer over: 4 vergelijkingen om te weten dat 40 ontbreekt, tegen 10 bij lineair zoeken.
Halveren gaat snel
Na één vergelijking is hoogstens de helft van de lijst over, na twee een kwart, na k hoogstens ongeveer n/2ᵏ. Het zoeken stopt als er niets meer over is, dus het heeft hoogstens ⌊log₂ n⌋ + 1 vergelijkingen nodig: 6 voor 40 waarden, 10 voor 1.000, 20 voor een miljoen en 30 voor een miljard. Een twee keer zo lange lijst kost maar één vergelijking meer. Dat schrijf je als O(log n).
Makkelijk uit te leggen, lastig om goed te doen
John Mauchly beschreef binair zoeken in 1946, maar volgens Donald Knuth werd de eerste versie die voor elke lijstlengte werkte pas in 1962 gepubliceerd. Jon Bentley ontdekte later dat maar ongeveer één op de tien professionele programmeurs het correct schreef: de eindvoorwaarden en het plus of min één bij het doorsnijden van de helften gaan makkelijk mis. In 2006 liet Joshua Bloch zien dat de gebruikelijke manier om het midden te vinden, (low + high) / 2, bij heel lange lijsten kan overlopen (overflow), een bug die jarenlang in de Java-bibliotheek had gezeten. Wie low + (high − low) / 2 schrijft, zoals de app doet, vermijdt dat.
Varianten en toepassingen
Bij dubbele waarden vindt binair zoeken een van de treffers; versies die links of rechts doorgaan, vinden de eerste of de laatste, of de plek waar een ontbrekende waarde zou moeten komen. Hetzelfde halveringsidee vindt de wortel van een vergelijking (bisectie), de versie waarin een bug voor het eerst opdook (git bisect), en het antwoord op veel optimalisatiepuzzels. Binaire zoekbomen slaan gegevens zo op dat elke opzoeking hetzelfde halveringspad volgt.
Probeer het zelf
Open de app, kies een waarde bij Zoek naar en druk op Stap. Het gearceerde deel is waar de gezochte waarde nog kan staan; de middelste waarde is gemarkeerd, en de helft die is uitgesloten vervaagt. De tegels tonen hoeveel waarden nog mogelijk zijn en hoeveel vergelijkingen lineair zoeken voor dezelfde waarde nodig zou hebben. Zoek naar een ontbrekende waarde, of gebruik 40 staven, om het verschil te zien groeien.
Veelgestelde vragen
Wat is de tijdscomplexiteit van binair zoeken?
O(log n): hoogstens ⌊log₂ n⌋ + 1 vergelijkingen voor n waarden. In het beste geval is het één vergelijking, als de gezochte waarde in het midden staat. De iteratieve versie heeft O(1) extra geheugen nodig.
Wat is het verschil tussen binair zoeken en lineair zoeken?
Lineair zoeken bekijkt elke waarde om de beurt en werkt op elke lijst, maar kan n vergelijkingen nodig hebben. Binair zoeken werkt alleen op een gesorteerde lijst, maar sluit bij elke vergelijking de helft van wat er over is uit, dus heeft het er ongeveer log₂ n nodig.
Loont het om een lijst te sorteren alleen voor binair zoeken?
Alleen als je er vaak in zoekt. Sorteren kost ongeveer n log n stappen, meer dan één keer lineair zoeken. Is de lijst eenmaal gesorteerd, dan is elke zoekopdracht daarna heel goedkoop.
Werkt binair zoeken ook op andere dingen dan lijsten?
Ja, op alles waarbij een test je vertelt aan welke kant van het antwoord je zit: een reeks getallen, de versies van een programma, of de gokken in een hoger-lager-spel.
Klaar om het te proberen?
Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.
Probeer binair zoeken