4.3 Bouwsteen 1 — laag en hoog
Leerdoel: je weet welke twee variabelen je nodig hebt om het zoekgebied bij te houden, en hoe je ze initialiseert.
Wat we willen
Bij binair zoeken praten we over een zoekgebied — het stuk lijst dat nog overblijft. We hebben twee getallen nodig om dat gebied te beschrijven:
laag: de eerste index die we nog moeten bekijken.hoog: de laatste index die we nog moeten bekijken.
In het begin is dat gebied de hele lijst.
Voorspel
Wat denk je dat dit print?
lijst = [1, 3, 5, 7, 9, 11, 13, 15]
laag = 0
hoog = len(lijst) - 1
print(laag, hoog)
Antwoord
0 7
laag = 0— de eerste index in een Python-lijst.hoog = len(lijst) - 1— de laatste index.len(lijst)is 8, dushoogis 7. Niet 8: een lijst van lengte 8 heeft indexen 0 t/m 7.
Run
Waarom -1?
hoog = len(lijst) - 1
Python-lijsten zijn 0-geïndexeerd: een lijst met 8 elementen heeft
indexen 0, 1, 2, 3, 4, 5, 6, 7 — niet 8. Als je lijst[8] opvraagt,
krijg je een IndexError.
Experimenteer
Wat valt op bij de lege lijst?
hoog wordt -1 (want len([]) - 1 = -1). Dat is meteen een signaal:
laag > hoog betekent "het zoekgebied is leeg". Hier hoeft het algoritme
dus nooit een ronde te doen — meteen "niet gevonden" returnen.
Bouwsteen model
Zoekgrenzen
Bereken de eerste en laatste geldige index.
Het zoekgebied loopt van index 0 tot 7.
Laag en hoog omsluiten het deel van de lijst dat nog mogelijk is.
Input grenzen([1, 3, 5, 7, 9, 11, 13, 15])
Verwacht [0, 7]
Input grenzen([42])
Verwacht [0, 0]
Input grenzen([])
Verwacht [0, -1]
Wat nu nog mist
We hebben grenzen, maar doen er nog niets mee. In de volgende stap berekenen we het midden van het zoekgebied.
Door naar bouwsteen 2: het midden.