Ga naar hoofdinhoud

Stellingen — toets je begrip

Leerdoel: je toetst of je het idee van binair zoeken (halveren) snapt, voordat je gaat programmeren.

Stelling 1​

"Binair zoeken werkt ook op een ongesorteerde lijst."

Antwoord

Onjuist. Het algoritme gaat ervan uit: "als het midden te hoog is, moet het doel links liggen". Die aanname klopt alleen als de lijst gesorteerd is. Op een rommelige lijst krijg je willekeurige antwoorden.

Stelling 2​

"Bij een lijst van 1000 elementen heb je in het ergste geval maximaal 10 stappen nodig."

Antwoord

Juist. Elke stap halveert het zoekgebied. Hoe vaak kun je 1000 halveren voor er 1 over is? Tien keer, want 2¹⁰ = 1024. Tien stappen dus, ook als het doel niet bestaat.

Stelling 3​

"Als een waarde meerdere keren voorkomt, geeft binair zoeken altijd de eerste voorkomende index."

Antwoord

Onjuist. Welke index je krijgt, hangt af van waar het midden toevallig landt. Het kan elk van de gelijke waardes zijn. Wil je per se de eerste? Dan moet je het algoritme aanpassen. Dat is de uitdaging bij Bouw zelf.

Stelling 4​

"Voor een lijst van 8 elementen zijn er maximaal 8 stappen nodig."

Antwoord

Onjuist. Voor 8 elementen zijn er maximaal 4 stappen nodig. Bij een lijst van 8:

  • Na stap 1 blijven er 4 elementen over.
  • Na stap 2 nog 2.
  • Na stap 3 nog 1.
  • Stap 4 vergelijkt dat laatste element, en dan ben je klaar.

Veel mensen schatten 3 omdat 2³ = 8, maar na 3 halveringen ligt er nog één element dat je nog moet bekijken. Vandaar de vierde stap.

Het zou lineair zoeken zijn dat tot 8 stappen nodig heeft.

Stelling 5​

"Bij elke stap valt ongeveer de helft van het zoekgebied af."

Antwoord

Juist. Ongeveer, niet precies: bij een oneven aantal elementen is de ene helft één groter dan de andere, en het midden zelf valt ook af. Voor het idee maakt dat niet uit: elke stap laat ongeveer de helft over.

Stelling 6​

"Binair zoeken is een soort recept dat je in je hoofd kunt uitvoeren, op elke gesorteerde lijst."

Antwoord

Juist. Een algoritme is precies dat: een stappenplan dat je mechanisch kunt volgen. Probeer het zelf: gesorteerde lijst maken, doel kiezen, met pen en papier de stappen volgen. Snap je hoe laag, hoog en midden veranderen, dan snap je het algoritme.

Door naar de eerste bouwsteen.