Stellingen — toets je begrip

Leerdoel: je toetst of je het idee van lineair zoeken snapt, voordat je gaat programmeren. Beantwoord elke stelling eerst zelf, klap dan open.

Stelling 1

"Lineair zoeken werkt alleen op gesorteerde lijsten."

Antwoord

Onjuist. Lineair zoeken bekijkt elk element apart — de volgorde maakt niet uit. Dat is juist het voordeel: het werkt altijd, ook op rommelige lijsten.

Stelling 2

"Als de waarde meerdere keren in de lijst staat, geeft lineair zoeken alle posities terug."

Antwoord

Onjuist. Standaard stopt het algoritme bij de eerste match — die index geef je terug. Wil je alle posities? Dan moet je het algoritme aanpassen. Dat doe je bij Bouw zelf.

Stelling 3

"In het ergste geval moet je elk element bekijken."

Antwoord

Juist. Het ergste geval is wanneer het doel achteraan staat — of helemaal niet in de lijst voorkomt. Dan moet je elke positie bezoeken voor je zekerheid hebt.

Twee keer zo'n lange lijst betekent in het ergste geval twee keer zoveel werk. Het werk groeit lineair mee met de lijst, en daar komt de naam vandaan.

Stelling 4

"Bij een lege lijst crasht het algoritme."

Antwoord

Onjuist. Een lege lijst betekent: niets om te bekijken → meteen "niet gevonden", dus -1. Geen crash.

Stelling 5

"De gemiddelde positie waarop je een willekeurig getal vindt, ligt in het midden van de lijst."

Antwoord

Juist. Als het doel willekeurig ergens in de lijst staat, is het gemiddeld ongeveer halverwege. Dus voor n elementen kijk je gemiddeld naar n/2 elementen voor je het vindt. Twee keer zo'n lange lijst is nog steeds twee keer zoveel werk; die factor 2 verandert daar niets aan.

Stelling 6

"Als het doel niet in de lijst staat, weet je dat pas na het laatste element."

Antwoord

Juist. Zolang er nog een element over is, kan het doel daar staan. Pas als je alles hebt gezien zonder match, mag je "niet gevonden" zeggen. Daarom is "niet gevonden" straks een eigen bouwsteen, ná de lus.

Door naar de eerste bouwsteen.