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 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.

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

Implementatie

In de volgende implementaties wordt de lijst {1, 9, 2, 3, 5, 6} doorzocht om te kijken of '3' voorkomt.

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;

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

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

Implementatie in C#

static void Main(string[] args)
{
  byte[] tabel = {4, 8, 2, 6, 7};
  byte gezocht = 7;
  if (GezochtGevonden(tabel, gezocht))
  {
    Console.Write("Gevonden");
  } else {
    Console.Write("Niet gevonden");
  }
}

private bool GezochtGevonden(byte[] tabel, byte gezocht)
{
  for (byte i = 0; i < tabel.Length; i++)
  {
    if (tabel[i] == gezocht)
    {
      return true;
    }
  }
  return false;
}/*GezochtGevonden*/

Zie ook

• Zoeken in lijsten