Lineair zoeken

Lineair zoeken doe je als je een naam zoekt op een ongesorteerde lijst: begin bovenaan en lees naar beneden tot je hem vindt. Het is de eenvoudigste zoekmethode die er is, het werkt op elke lijst, en voor korte lijsten is het vaak alles wat je nodig hebt.

Staven van een lijst die een voor een vanaf het begin worden gecontroleerd, de gecontroleerde staven vervaagd, een stippellijn op de hoogte van de doelwaarde en de gevonden staaf uitgelicht
Staven van een lijst die een voor een vanaf het begin worden gecontroleerd, de gecontroleerde staven vervaagd, een stippellijn op de hoogte van de doelwaarde en de gevonden staaf uitgelicht

Het idee

Vergelijk de doelwaarde met de eerste waarde van de lijst. Zijn ze gelijk, stop dan: de doelwaarde staat op plek 1. Vergelijk haar anders met de tweede waarde, dan de derde, enzovoort. Komt ook de laatste waarde niet overeen, dan staat de doelwaarde niet in de lijst. Je hoeft vooraf niets over de lijst te weten: ze hoeft niet gesorteerd te zijn, en de waarden kunnen alles zijn wat je op gelijkheid kunt vergelijken.

Een voorbeeld

Zoek 4 in 5, 1, 4, 2, 8. Is 5 gelijk aan 4? Nee. En 1? Nee. En 4? Ja: gevonden op plek 3 na 3 vergelijkingen. Zoek nu 7 in dezelfde lijst. Elk van de vijf waarden wordt gecontroleerd en geen enkele komt overeen, dus na 5 vergelijkingen is het antwoord dat 7 er niet in staat.

Hoeveel vergelijkingen

Een waarde op plek k vinden kost k vergelijkingen. Als de doelwaarde op elke plek even waarschijnlijk is, zijn dat gemiddeld (n + 1)/2 vergelijkingen: 20,5 bij 40 waarden. Een ontbrekende waarde kost altijd n, want pas na de laatste vergelijking is zeker dat geen enkele waarde overeenkwam. De kosten groeien dus evenredig met de lengte van de lijst, wat je schrijft als O(n).

Sneller zoeken vraagt om ordening

Lineair zoeken kan niets overslaan, want in een ongesorteerde lijst kan elke waarde overal staan. Is een lijst gesorteerd, dan vertelt een vergelijking meer dan gelijk of niet: ze vertelt aan welke kant de doelwaarde ligt. Binair zoeken gebruikt dat om de lijst bij elke stap te halveren en heeft ongeveer log₂ n vergelijkingen nodig, hooguit 6 bij 40 waarden. Sorteren kost echter ook tijd, dus voor een lijst die maar één keer wordt doorzocht, is lineair zoeken vaak de betere keuze.

Kleine verbeteringen

Een versie met schildwacht zet de doelwaarde vóór het zoeken aan het eind van de lijst, zodat de lus alleen op een treffer hoeft te testen en niet ook op het eind van de lijst. Een waarde bij elke vondst één plek naar voren zetten, of helemaal vooraan, maakt vaak gezochte waarden na verloop van tijd goedkoper. Geen van beide verandert het slechtste geval van n vergelijkingen.

Probeer het zelf

Open de app, kies een waarde bij Zoek naar en druk op Stap. De stippellijn toont de hoogte van de doelwaarde, elke waarde licht op terwijl ze wordt gecontroleerd en vervaagt zodra ze is uitgesloten, en een treffer wordt groen. Zoek een waarde die niet in de lijst staat om een volledige doorloop te zien, of zet Stop bij de eerste treffer uit en gebruik weinig unieke waarden om meerdere treffers te vinden.

Veelgestelde vragen

Wat is de tijdcomplexiteit van lineair zoeken?

O(n) in het slechtste en gemiddelde geval, en O(1) in het beste geval, als de doelwaarde de eerste waarde is. Het heeft geen extra geheugen nodig.

Wat is het verschil tussen lineair zoeken en binair zoeken?

Lineair zoeken controleert elke waarde op volgorde en werkt op elke lijst. Binair zoeken werkt alleen op een gesorteerde lijst, maar halveert bij elke stap het deel waarin de doelwaarde kan staan, dus het heeft ongeveer log₂ n vergelijkingen nodig in plaats van tot n.

Heeft lineair zoeken een gesorteerde lijst nodig?

Nee. Dat is het grootste voordeel. Op een gesorteerde lijst kan het stoppen zodra het voorbij de plek is waar de doelwaarde zou staan, maar het blijft trager dan binair zoeken.

Waar wordt lineair zoeken gebruikt?

Overal waar lijsten kort of ongesorteerd zijn: een item vinden in een kleine array, een bestand of stream doorlopen die alleen op volgorde te lezen is, of elk element op een voorwaarde controleren. Veel bibliotheekfuncties, zoals indexOf in JavaScript en list.index in Python, zijn lineaire zoekacties.

Klaar om het te proberen?

Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.

Probeer lineair zoeken