Cheatsheet — binair zoeken

Snelle referentie. Klap open wat je nodig hebt.

Het algoritme zelf

De canonieke implementatie

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

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

1. Grenzen — laag en hoog

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

hoog is de laatste index, niet de lengte.

2. 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 → //.

3. Vergelijken en helft kiezen

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.

4. De while-lus

while laag <= hoog:
    ...

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

5. Niet gevonden

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

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

Python-syntax

Tuples terug geven

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

Uitpakken:

idx, stp = binair_zoek_met_stappen(getallen, 7)

break

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 lineair zoeken voor het contrast — en dan ben je klaar voor de volgende algoritmes die we later toevoegen.