Ga naar hoofdinhoud

Er gaat iets mis — top-3 fouten

Leerdoel: je herkent de klassieke valkuilen van binair zoeken.

1. Oneindige lus (laag = midden in plaats van midden + 1)​

Geen foutmelding — de Python loopt gewoon oneindig door. Browser-tab hangt. Druk op Reset als dit gebeurt.

Voorbeeld + uitleg
elif lijst[midden] < doel:
    laag = midden     # ← fout!

Stel laag = 1, hoog = 2. Dan midden = (1+2) // 2 = 1. Doen we laag = midden, dan blijft laag = 1. Volgende ronde: weer midden = 1. Niets verandert — eindeloos.

Fix: laag = midden + 1. Door het al-onderzochte midden weg te gooien, moet het zoekgebied krimpen.

Waarom werkt dat?

  • lijst[midden] is al gecontroleerd — die hoef je nooit meer mee te nemen.
  • Door + 1 of - 1 te doen, krimpt het zoekgebied gegarandeerd met minstens 1 element per stap → de lus stopt altijd.

2. laag <= hoog vs laag < hoog​

Geen Python-foutmelding — wél een logische fout bij sommige inputs.

Voorbeeld + uitleg
while laag < hoog:   # ← < in plaats van <=
    ...

Probeer dit op [5] met doel = 5. Aan het begin: laag = 0, hoog = 0.

  • Met <: de lus draait 0 keer → meteen return -1. Bug — 5 staat er wél in.
  • Met <=: de lus draait 1 keer, vindt het, returnt 0. Goed.

Fix: while laag <= hoog. Bij laag == hoog is er nog één element over om te bekijken.

3. Ongesorteerde lijst meegeven​

Geen foutmelding — gewoon fout antwoord. Dit is de gevaarlijkste soort bug, omdat hij stilletjes verkeerde dingen doet.

Voorbeeld + uitleg
binair_zoek([3, 1, 4, 1, 5], 4)   # output kan -1 zijn, of toevallig 2

Het algoritme veronderstelt: als lijst[midden] < doel, dan moet het doel in de rechter helft zitten. Die aanname klopt alleen als de lijst gesorteerd is.

Fix: zorg dat je input gesorteerd is.

lijst = sorted(jouw_lijst)
binair_zoek(lijst, doel)

Of, als je vaak zoekt, sorteer één keer en bewaar de gesorteerde versie. Het sorteren kost O(n log n), maar daarna is elk zoeken O(log n) — bij veel zoekopdrachten loont dat.

Door naar stap 12: cheatsheet →