Lineair zoeken
In de informatica is lineair zoeken (of sequentieel zoeken) een zoekalgoritme om een hoeveelheid data (meestal lijsten) te doorzoeken. Het algoritme begint bij het eerste element in een lijst en bekijkt elk volgend element totdat het gezochte element gevonden is.
In het slechtste geval, worst case, moeten alle elementen bekeken worden; de benodigde tijd is hierdoor O(n) waarbij n het aantal elementen in de lijst is. In het beste geval is het gezochte element het eerste element in de lijst waardoor er slechts 1 vergelijking nodig is. Wanneer de elementen willekeurig over de lijst verdeeld zijn, zijn er gemiddeld n/2 vergelijkingen nodig om het element te vinden.
Lineair zoeken kan worden gebruikt om een ongesorteerde lijst te doorzoeken. Om een lange gesorteerde lijst te doorzoeken is binair zoeken het meest efficient. Als n groot is, kan het efficiënter zijn om de lijst eerst te sorteren (met een sorteeralgoritme) en dan binair zoeken te gebruiken in plaats van lineair zoeken. Een andere manier is een hashtabel maken en daarin waarden op te zoeken.
Inhoud |
[bewerk] Werking
Bij het doorlopen van de lijst wordt bij het eerste element begonnen. Indien dat element niet het gezochte element is, bekijkt het algoritme het volgende element. Zo wordt de hele lijst afgelopen tot het gevonden is (of niet, indien het element zich niet in de lijst bevindt). Het aantal bewerkingen is dus (in het slechtste geval) evenredig met het aantal elementen in de lijst, n. Dit is een eerstegraadsfunctie of een rechte wat ook de term lineair verklaart.
In pseudocode verloopt het lineair zoeken in lijst L als volgt:
for each element in lijst L
if element == gezochte element
return gevonden
return niet gevonden
[bewerk] Implementatie
In de volgende implementaties wordt de lijst {1, 9, 2, 3, 5, 6} doorzocht om te kijken of '3' voorkomt.
[bewerk] Implementatie in C
int lijst[] = {1,9,2,3,5,6};
int gezocht = 3;
int lengte = 6;
for (int n = 0; n < lengte; n++) {
if (lijst[n] == gezocht) {
return true;
}
}
return false;
[bewerk] Implementatie in Haskell
De volgende functie levert op of een element voorkomt in een lijst:
zoekLijst :: [Int] -> Int -> Bool
zoekLijst [] _ = False
zoekLijst (x:xs) n | x == n = True
| otherwise = zoekLijst xs n
In het voorbeeld zou de aanroep van deze functie zijn: zoekLijst [1,9,2,3,5,6] 3
[bewerk] Implementatie in VBScript
De volgende functie geeft een boolean terug die true is als het element voorkomt in de lijst
function zoekLijst(arrLijst, intZoeken)
for i = 0 to UBound(arrLijst)
if arrLijst(i) = intZoeken then
return true
end if
next
return false
end function
