Bouwsteen 3 — vergelijken en helft kiezen

Leerdoel: je vergelijkt het midden-element met het doel en past laag of hoog aan om de juiste helft te behouden.

Wat we willen

Drie mogelijke uitkomsten van een vergelijking tussen lijst[midden] en doel:

Geval	Wat doen?
lijst[midden] == doel	Gevonden! We hebben hem.
lijst[midden] < doel	Het doel is groter → ligt in de rechter helft → laag = midden + 1
lijst[midden] > doel	Het doel is kleiner → ligt in de linker helft → hoog = midden - 1

Waarom + 1 en - 1?

Heel belangrijk: we hebben lijst[midden] net al bekeken. Die index hoeven we nooit meer te zien. Door + 1 of - 1 doen we hem netjes weg.

(Sla je + 1 over en zet je laag = midden, dan krijg je een oneindige lus. Daar komen we in stap 5 bij "Veelgemaakte fouten" nog op terug.)

Voorspel

We zoeken doel = 11 in [1, 3, 5, 7, 9, 11, 13, 15]. Wat denk je dat dit print?

lijst = [1, 3, 5, 7, 9, 11, 13, 15]
laag = 0
hoog = 7
doel = 11

midden = (laag + hoog) // 2
if lijst[midden] == doel:
    print("gevonden op", midden)
elif lijst[midden] < doel:
    laag = midden + 1
else:
    hoog = midden - 1

print(f"na 1 stap: laag={laag}, hoog={hoog}")

Antwoord

na 1 stap: laag=4, hoog=7

• midden = (0+7) // 2 = 3
• lijst[3] = 7
• 7 < 11 → we komen in de elif
• laag = midden + 1 = 4
• hoog blijft 7

Het zoekgebied is nu indexen 4 t/m 7 — de rechter helft. Halveerd!

Run

Python

Code-omgeving wordt voorbereid…

Experimenteer

Verander doel in 3 (zou linker helft moeten kiezen) en in 7 (direct gevonden).

Wat nu nog mist

We hebben net één stap gedaan. Maar één halvering is meestal niet genoeg. We willen dat dit blijft herhalen — totdat we het vinden of het zoekgebied leeg is. Daarvoor hebben we een lus nodig.

Door naar bouwsteen 4: de while-lus →