BinarySearch, 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
Speicher Ω(1) Θ(1) Ο(1)
Laufzeit Ω(logn) Θ(logn) Ο(logn)
Vergleiche (found) logn logn logn
Vergleiche (not found) logn logn logn

int binarysearch(field A, int l, int r, element ele) {
  sort(A, l, r);
  while (l < r) do {
    q:= (l+r) div 2;
    if (A[q] >= ele) then {
      r:= q;
    } else {
      l:= q+1;
    }
  }
  if (A[l] = ele) then {
    return l;
  } else {
    return -1;
  }
}

Variante 2.b (rekusiv)
Typ standard
Eigenschaften rekursiv, nicht parallelisierbar
Datenstrukturen Felder
Speicher Ω(logn) Θ(logn) Ο(logn)
Laufzeit Ω(logn) Θ(logn) Ο(logn)
Vergleiche (found) logn logn logn
Vergleiche (not found) logn logn logn

int binarysearch(field A, int l, int r, element ele) {
  sort(A, l, r);
  return binary(A, l, r, ele);
}

int binary(field A, int l, int r, element ele) {
  if (l < r) then {
    q:= (l+r) div 2;
    if (A[q] >= ele) then {
      return binary(A, l, q, ele);
    } else {
      return binary(A, q+1, r, ele);
    }
  } else if (A[l] = ele) then {
    return l;
  } else {
    return -1;
  }
}