Klassiek binair zoeken zonder fouten

Binair zoeken vindt een waarde in een gesorteerde lijst door het bereik bij elke stap te halveren. Zo wordt een trage scan van O(n) een snelle zoekactie van O(log n).

Binair zoeken werkt alleen op gesorteerde gegevens. Als de lijst niet geordend is, moet je die eerst sorteren; anders is het resultaat betekenisloos en fout.

Begin met twee pointers: low op index 0 en high op de laatste index. De doelwaarde bevindt zich, als die aanwezig is, altijd daartussen.

Bereken mid als low + (high - low) // 2. In Python is overflow geen probleem, maar deze vorm is overal een veilige gewoonte.

Vergelijk a[mid] met de doelwaarde. Je hebt de waarde gevonden, de waarde is te klein of de waarde is te groot. Elk geval verkleint het bereik op een andere manier.

Als a[mid] kleiner is dan de doelwaarde, moet het antwoord rechts staan. Verplaats low naar mid + 1 en gooi de linkerhelft weg.

Als a[mid] groter is dan de doelwaarde, zoek je in de linkerhelft. Verplaats high naar mid - 1, zodat je mid nooit opnieuw controleert.

Ga door zolang low kleiner dan of gelijk aan high is. Zodra ze elkaar kruisen, is het bereik leeg en staat de doelwaarde er niet in.

Als de lus eindigt zonder overeenkomst, ontbreekt de waarde. Geef -1 terug als vaste afspraak, zodat aanroepen succes en mislukking van elkaar kunnen onderscheiden.

De klassieke fout is dat je de +1 of -1 vergeet wanneer je een pointer verplaatst. Laat je die weg, dan wordt mid eindeloos opnieuw gecontroleerd en ontstaat er een oneindige lus.

Voor een eenvoudige controle of een waarde voorkomt, bevat Pythons module bisect al foutvrij zoekwerk. Schrijf de lus alleen zelf als je aangepaste logica nodig hebt.

Je kunt nu low en high instellen, mid veilig berekenen, de juiste kant verkleinen en de valkuil van één te veel of te weinig vermijden. Je beheerst logaritmisch zoeken. 🎯