Ga naar hoofdinhoud

Lineair zoeken — het idee

Leerdoel: je begrijpt wat lineair zoeken is, in mensentaal. Nog geen Python — eerst snappen, dan pas programmeren.

Het verhaal​

Je hebt een boekenkast waarin de boeken niet op alfabet staan. Je zoekt "De ontdekking van de hemel". Wat doe je?

Je pakt het eerste boek, kijkt naar de titel — niet de juiste. Tweede boek, kijken — niet de juiste. Net zo lang tot je het boek vindt, of tot je bij het laatste boek bent geweest en weet dat het er niet is.

Dat is lineair zoeken in één zin: één voor één, van begin tot eind, tot je vindt wat je zoekt.

Visualisatie​

We zoeken het getal 5 in deze lijst:

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

stap 1:  [(3), 1 , 4 , 1 , 5 , 9 , 2 , 6 ]   3 == 5?  nee
stap 2:  [ 3 ,(1), 4 , 1 , 5 , 9 , 2 , 6 ]   1 == 5?  nee
stap 3:  [ 3 , 1 ,(4), 1 , 5 , 9 , 2 , 6 ]   4 == 5?  nee
stap 4:  [ 3 , 1 , 4 ,(1), 5 , 9 , 2 , 6 ]   1 == 5?  nee
stap 5:  [ 3 , 1 , 4 , 1 ,(5), 9 , 2 , 6 ]   5 == 5?  JA → index 4

In stap 5 vinden we het, op index 4.

En als het er niet in zit?​

En nu zoeken we 7:

zoeken: 7
stap 1:  3 == 7?  nee
stap 2:  1 == 7?  nee
stap 3:  4 == 7?  nee
stap 4:  1 == 7?  nee
stap 5:  5 == 7?  nee
stap 6:  9 == 7?  nee
stap 7:  2 == 7?  nee
stap 8:  6 == 7?  nee
→ alles gehad, niet gevonden

Alle elementen bekeken en niets gevonden. Dus: "7 zit er niet in". We spreken meestal af om dan -1 terug te geven — een duidelijk "niet-gevonden"-signaal (want geldige indexen beginnen bij 0).

Twee dingen om te onthouden​

  1. Eén voor één door de lijst lopen, zonder slimmigheden.
  2. Stoppen bij de eerste match, of -1 teruggeven als je het einde haalt.
Wanneer is dit eigenlijk slim?
  • Bij kleine lijsten, want het verschil met een sneller algoritme merk je toch niet.
  • Bij ongesorteerde lijsten, want slimmere algoritmes (zoals binair zoeken) werken daar niet.
  • Als je toch alles moet bekijken, bijvoorbeeld om te tellen hoe vaak iets voorkomt.
info

Liever eerst zonder computer? Voer lineair zoeken uit met een kaartspel 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":

  1. Bouwsteen 1 — door de lijst lopen
  2. Bouwsteen 2 — vergelijken met het doel
  3. Bouwsteen 3 — de index teruggeven
  4. Bouwsteen 4 — het "niet gevonden"-geval

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

Door naar bekijk het algoritme.