BinarySearch, Variante 1 (Original)

Hierbei handelt es sich um die Original-Variante.

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

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