Vyhledávací algoritmy: Sekvenční vyhledávání

Vyhedávat je potřeba asi tak stejně jako třídit a tyto dvě činnosti spolu velmi souvisí. Často jdou ruku v ruce. U sekvenčního vyhledávání to ovšem není nutné, funguje i na nesetříděné množině.

Sekvenční vyhledávání je nejjednodušší vyhledávací algoritmus a většinou je to první způsob, který nás napadne. Nevyžaduje totiž žádné složité přemýšlení a je velice jednoduchý na implementaci.

Složitost sekvenčního vyhledávání je:
Asimptotická:Ο(n), Θ(n) a Ω(0)
Absolutní:Ο(n), Θ(n/2) a Ω(0)

Princip je velmi jednoduchý, prostě si množinu, ve které prvek hledáme, sekvenčně projdeme prvek po prvku, dokud nenarazíme na hledaný prvek nebo konec množiny. Z toho vyplývá ta záhadná složitost. Hledaný prvek může být hned prvním, na který narazíme, nebo taky posledním. Statisticky sečteno a podtrženo, průměrně projdeme polovinu množiny.

Ukončení může být několik a záleží na našich požadavcích. Buďto můžeme vrátit přímo daný prvek, nebo třeba index v poli. Krom toho můžeme vracet jenom příznak true při nalezení prvku a false pokud není. Také je možné mít několik stejných prvků v jedné skupině, ve které vyhledáváme, potom můžeme použit všechny předchozí principy na první nalezený prvek anebo vracet množinu indexů nebo počet nalezených prvků, ale potom musíme vždy projít celou skupinu a složitost je potom Ο(n), Θ(n) a Ω(n).

Vývojový diagram: znázorňuje variantu vrátící první prvek/odkaz na který narazí.

Vývojový diagram:

public static Object sequentialSearch (Object[] set, Object searched) {
  for (int i = 0; i < set.length; i++) {
    if (searched == set [i]) {
      return set [i];
    }
  }
    return null;
}

function  sequentialSearch(scannedSet: Array of Integer;
			   searched: Integer): Integer;
var i: Integer;
begin
for i := Low(scannedSet) to High(scannedSet) do 
  if scannedSet[i] = searched then
    begin
    SeqSearch := scannedSet[i];
    Exit;
    end;
sequentialSearch nil;
end;