4.12 Cheatsheet — binair zoeken

Snelle referentie. Klap open wat je nodig hebt.

Het algoritme zelf

De canonieke implementatie (binair_zoek)

def binair_zoek(lijst, doel):
    laag = 0
    hoog = len(lijst) - 1
    while laag <= hoog:
        midden = (laag + hoog) // 2
        if lijst[midden] == doel:
            return midden
        elif lijst[midden] < doel:
            laag = midden + 1
        else:
            hoog = midden - 1
    return -1

Recursieve variant (binair_zoek_rec)

def binair_zoek_rec(lijst, doel, laag=0, hoog=None):
    if hoog is None:
        hoog = len(lijst) - 1
    if laag > hoog:
        return -1
    midden = (laag + hoog) // 2
    if lijst[midden] == doel:
        return midden
    elif lijst[midden] < doel:
        return binair_zoek_rec(lijst, doel, midden + 1, hoog)
    else:
        return binair_zoek_rec(lijst, doel, laag, midden - 1)

De bouwstenen

Grenzen — laag en hoog

laag = 0
hoog = len(lijst) - 1   # let op de -1!

hoog is de laatste index, niet de lengte.

Het midden berekenen (//)

midden = (laag + hoog) // 2

• // → integer-deling (7 // 2 == 3)
• / → gewone deling (7 / 2 == 3.5)

Voor een index heb je een geheel getal nodig → //.

Vergelijken en helft kiezen (if/elif/else)

if lijst[midden] == doel:
    return midden
elif lijst[midden] < doel:
    laag = midden + 1     # zoek rechts
else:
    hoog = midden - 1     # zoek links

De + 1 en - 1 zijn cruciaal — anders oneindige lus.

De while-lus (while laag <= hoog)

while laag <= hoog:
    ...

Gebruik <= — bij laag == hoog is er nog 1 element over.

Niet gevonden (return -1)

    return -1   # buiten de while, op functie-niveau

Wordt alleen bereikt als de while-lus stopt zonder match.

Python-syntax

Tuples terug geven (return a, b)

return (index, stappen)
# of zonder haakjes:
return index, stappen

Uitpakken:

idx, stp = binair_zoek_met_stappen(getallen, 7)

break — uit een lus springen

while voorwaarde:
    ...
    if klaar:
        break    # stop de lus direct

Eigenschappen

Voorwaarden

• Lijst moet gesorteerd zijn.
• Elementen moeten vergelijkbaar zijn met < en ==.

Hoe snel?

• Beste geval: doel staat op midden bij eerste stap → 1 vergelijking.
• Slechtste geval: ⌈log₂(n)⌉ vergelijkingen.
• We zeggen: O(log n).

n	max. vergelijkingen
10	4
100	7
1.000	10
1.000.000	20
1.000.000.000	30

Veelgemaakte fouten (snel)

Top-3 fouten

1. laag = midden zonder + 1 → oneindige lus.
2. while laag < hoog → mist het laatste element bij laag == hoog.
3. Ongesorteerde input → fout antwoord, geen exception.

---

Klaar? Probeer ook selection sort — een algoritme dat een lijst zélf gesorteerd maakt.