Aufgabe:
Analyse von Algorithmen
Ternäre Suche
Wir übertragen die Idee der Binärsuche auf die Suche in einer von drei Teilen.
boolean ternarySearch(int[] a, int low, int high, int v) {
if (low > high) return false;
int mid1 = low + (high - low) / 3;
if (a[mid1] == v) return true;
if (v < a[mid1]) {
return ternarySearch(a, low, mid1 - 1, v);
}
int mid2 = low + 2 * (high - low) / 3;
if (a[mid2] == v) return true;
if (v < a[mid2]) {
return ternarySearch(a, mid1 + 1, mid2 - 1, v);
}
return ternarySearch(a, mid2 + 1, high, v);
}
Analysieren Sie die Komplexität (Anzahl an Vergleichen – worst-case!). Gehen Sie wie folgt vor:
• Erstellen Sie die Rekursionsgleichung (analog zur binären Suche)
• Versuchen Sie, eine Lösung zu „erraten“ – Denken Sie an Binärsuche
Ansatz:
Die erste Frage habe ich beantwortet mit der Rekursionsgleichung T(n) = T (n/3) + 4
Ich weiß nicht genau was man bei der zweiten Frage tun soll? Mit der Rekursionsgleichung irgendwie eine Lösung erraten? Kann mir bitte jemand weiterhelfen?
Vielen Dank im Voraus!
