Lineair zoeken
Uit Wikipedia, de vrije encyclopedia
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 bisectie (binair zoeken) het meest efficiënt. 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.