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