Het complete algoritme

Leerdoel: je herkent alle bouwstenen die je hebt geleerd en ziet ze samen werken. Daarna onderzoek je het algoritme als geheel.

Alles samen

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

Zie je de bouwstenen?

• Regels 2-3 → bouwsteen 1: grenzen laag en hoog
• Regel 5 → bouwsteen 2: het midden berekenen
• Regels 6-11 → bouwsteen 3: vergelijken en de juiste helft kiezen
• Regel 4 → bouwsteen 4: de while-lus
• Regel 12 → bouwsteen 5: -1 bij niet gevonden

Run

Python

Code-omgeving wordt voorbereid…

Onderzoek

Speel met de code. Probeer in elk geval:

1. Wat gebeurt er op een lege lijst?
2. Wat gebeurt er op een lijst van één element?
3. Wat gebeurt er op een ongesorteerde lijst?

Python

Code-omgeving wordt voorbereid…

Wat zie je?

• Lege lijst → hoog = -1, dus laag (0) > hoog (-1) → while draait 0 keer → return -1. Veilig.
• Eén element → laag = hoog = 0, midden = 0. Check direct.
• Ongesorteerd → een toevallig antwoord, vaak verkeerd. Het algoritme is niet correct op ongesorteerde input.

Visualiseer de stappen

Soms helpt het om te zien hoeveel stappen er zijn. Hier draaien we het algoritme op lijsten van verschillende lengtes en plotten we het aantal stappen.

Python

Code-omgeving wordt voorbereid…

Wat zie je?

Op een logaritmische x-as zie je een rechte lijn. Dat is precies de definitie van O(log n): bij elke verdubbeling van n komt er één stap bij.

• 10 → 4 stappen
• 100 → 7 stappen
• 1000 → 10 stappen
• 10.000 → 14 stappen
• 100.000 → 17 stappen

Voor 100.000 elementen: 17 vergelijkingen in het ergste geval. Lineair zoeken zou er 100.000 doen. Factor ~6000.

Door naar stap 9: aanpassen →