Ga naar hoofdinhoud

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, dus hoog is 7. Niet 8! Een lijst van lengte 8 heeft indexen 0 t/m 7.

Run​

Python
Code-omgeving wordt voorbereid…

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​

Python
Code-omgeving wordt voorbereid…
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.

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 →