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