4.5 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 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).

Bouwsteen model

Helft kiezen

Vergelijk het midden en geef aan welk zoekgebied overblijft.

Stap 2/2Vergelijkingen 2Resultaat 5

01

13

25

37

49laag

511mid raak

613

715hoog

Midden is index 5

11 is gelijk aan 11. We geven index 5 terug.

Na de vergelijking wordt de linker- of rechterhelft weggegooid.

Feedback

def een_binaire_stap(lijst, doel, laag, hoog):
    # Return ["gevonden", midden], ["rechts", nieuw_laag, hoog] of ["links", laag, nieuw_hoog]
    # Schrijf je oplossing hier
    return None

def een_binaire_stap(lijst, doel, laag, hoog): # Return ["gevonden", midden], ["rechts", nieuw_laag, hoog] of ["links", laag, nieuw_hoog] # Schrijf je oplossing hier return None

rechter helft

Input een_binaire_stap([1, 3, 5, 7, 9, 11, 13, 15], 11, 0, 7)

Verwacht [rechts, 4, 7]

linker helft

Input een_binaire_stap([1, 3, 5, 7, 9, 11, 13, 15], 3, 0, 7)

Verwacht [links, 0, 2]

direct gevonden

Input een_binaire_stap([1, 3, 5, 7, 9], 5, 0, 4)

Verwacht [gevonden, 2]

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.