FMSearch, Variante 2 (Sortierung)

Hierbei handelt es sich um eine geringfügige Verbesserung. Die Idee ist einfach: Wenn das Feld sortiert vorliegt, kann eher festgestellt werden, ob das Element überhaupt gefunden werden kann.

Die Laufzeit für das Sortieren wird hier nicht berücksichtigt!

Variante 2.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) 1 n/2 n

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

Variante 2.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) 1 n/2 n

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