Wyszukiwanie liniowe

Jeśli nie dysponujemy żadną dodatkową wiedzą na temat zbioru, który chcemy przeszukiwać, niestety musimy sprawdzić wszystkie jego elementy.

function Szukaj(x, A[1..n])
begin
  for i:=1 to n do 
    if A[i]=x return i; 
  return brak poszukiwanego elementu; 
end

Oczywiście w pesymistycznym przypadku (np. gdy zbiór nie zawiera poszukiwanego elementu) koszt czasowy, to \( O(n) \).