Binair zoeken — het idee

Leerdoel: je begrijpt het idee van halveren bij zoeken, en waarom dat veel sneller kan dan lineair zoeken. Nog geen Python — eerst snappen.

Het verhaal

We doen een raadspel: ik denk aan een getal tussen 1 en 100. Bij elke gok zeg ik "hoger", "lager" of "goed.".

Wat is jouw eerste gok?

De slimste eerste gok

50, want daarmee valt in één klap de helft van alle mogelijkheden af.

Zeg ik "hoger", dan zit het tussen 51 en 100.
Zeg ik "lager", dan zit het tussen 1 en 49.

Je tweede gok gaat weer precies naar het midden van het overgebleven bereik. En zo verder.

Zo ben je er bij 100 getallen in hooguit zeven gokken (want 2⁷ = 128 ≥ 100).

Dat is binair zoeken in één zin: kies steeds het midden, halveer het zoekgebied, herhaal.

Belangrijke voorwaarde

Binair zoeken werkt alleen op een gesorteerde lijst. Anders zegt "het midden" geen betekenis — je weet niet of het doel links of rechts ligt.

Visualisatie — wel gevonden

We zoeken 7 in deze gesorteerde lijst:

zoeken: 7
lijst:  [ 1 , 3 , 5 , 7 , 9 , 11 , 13 , 15 ]
index:    0   1   2   3   4   5    6    7

stap 1: laag=0, hoog=7 → midden=3 → lijst[3]=7
        [ 1 , 3 , 5 ,(7), 9 , 11 , 13 , 15 ]   7 == 7?  JA → index 3

In één stap raak. Dat was geluk: 7 zat precies op het midden.

Visualisatie — niet gevonden

En nu zoeken we 4, die er niet in staat:

zoeken: 4
lijst:  [ 1 , 3 , 5 , 7 , 9 , 11 , 13 , 15 ]

stap 1: laag=0, hoog=7 → midden=3 → lijst[3]=7
        midden te hoog → kijk alleen nog links → hoog wordt 2

stap 2: laag=0, hoog=2 → midden=1 → lijst[1]=3
        midden te laag → kijk alleen nog rechts → laag wordt 2

stap 3: laag=2, hoog=2 → midden=2 → lijst[2]=5
        midden te hoog → hoog wordt 1
        laag > hoog → stop → niet gevonden → -1

Drie stappen, geen match. We zijn klaar.

Hoe snel?

Voor een lijst van 1.000.000 elementen:

	Lineair zoeken	Binair zoeken
Werkt op ongesorteerd	ja	nee
Max. vergelijkingen	1.000.000	~20
Snelheidsklasse	O(n)	O(log n)

Dat scheelt een factor 50.000. Bij een miljard zou het verschil al nog veel groter zijn — exponentieel groter zelfs.

info

Dit halveren voel je pas echt met kaarten in je handen: probeer de werkvorm in Zoeken en sorteren met kaarten.

Zo bouw je het op

De code bouw je in kleine stappen, elk op een eigen pagina in de map "Bouwen, stap voor stap":

Daarna zet je alles samen in Het complete algoritme, en ga je het aanpassen en zelf bouwen.

Door naar bekijk het algoritme.

Het verhaal​

Belangrijke voorwaarde​

Visualisatie — wel gevonden​

Visualisatie — niet gevonden​

Hoe snel?​

Zo bouw je het op​