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;
}
}
}
| |
|