FMSearch, Variante 1 (Original)

Hierbei handelt es sich um die Original-Variante.

Variante 1.a (iterativ)
Typ standard
Eigenschaften iterativ, nicht parallelisierbar
Datenstrukturen Felder, einfachverkettete Listen
Speicher Ω(1) Θ(1) Ο(1)
Laufzeit Ω(1) Θ(n) Ο(n)
Vergleiche (found) 1 n/2 n
Vergleiche (not found) n n n

int fmsearch(field A, int l, int r, element ele) {
  for i:=l to r do {
    if (A[i] = ele) then {
      return i;
    }
  }
  return -1;
}

Variante 1.b (rekursiv)
Typ standard
Eigenschaften rekursiv, nicht parallelisierbar
Datenstrukturen Felder, einfachverkettete Listen
Speicher Ω(1) Θ(n) Ο(n)
Laufzeit Ω(1) Θ(n) Ο(n)
Vergleiche (found) 1 n/2 n
Vergleiche (not found) n n n

int fmsearch(field A, int l, int r, element ele) {
  if (l > r) then {
    return -1;
  } else if (A[l] = ele) then {
    return l;
  } else {
    fmsearch(A,l+1,r,ele);
  }
}