Binäre Suche: Iterativ vs rekursiv?
Ich habe beides in Java implementiert, verstehe aber nicht, warum die rekursive Variante mehr als doppelt so schnell ist. Müsste es normalerweise nicht anders herum sein? Oder habe ich bei der iterativen Variante irgendetwas suboptimal gelöst?
public static int binarySearchIterative(int[] a, int z) {
int left = 0;
int right = a.length - 1;
while (left <= right) {
int midpoint = (int)((left + right) / 2);
if (z == a[midpoint]) {
return midpoint;
}
if (z < a[midpoint]) {
right = midpoint - 1;
}
else {
left = midpoint + 1;
}
}
return -1;
}
public static int binarySearchRecursive(int[] a, int z, int left, int right) {
int midpoint = (int)((left + right) / 2);
if (right < left) {
return -1;
}
if (z == a[midpoint]) {
return midpoint;
}
if (z < a[midpoint]) {
return binarySearchRecursive(a, z, left, midpoint - 1);
}
else {
return binarySearchRecursive(a, z, midpoint + 1, right);
}
}
1 Antwort
Vom Beitragsersteller als hilfreich ausgezeichnet
Nutzer, der sehr aktiv auf gutefrage ist
So auf die Schnelle kann ich dir das nicht beantworten. Aber mein Tipp wäre, dass du dir da einfach mal Debug-Meldungen reinschreibst oder das im Debugger durch gehst und prüfst, ob die Intervalle wirklich immer "optimal" verkleinert werden bei der iterativen Lösung.
Woher ich das weiß:Studium / Ausbildung – Informatikstudium
Danke, letztendlich war es nur ein Fehler bei der Messung der Zeiten. Es sieht so aus, dass die JVM wohl etwas Zeit zum „Einlaufen“ benötigt. Daher führe ich beide Funktionen einmal auf dasselbe zufällig erzeugte Array aus und erst danach führe ich sie nochmals aus, um zu messen. Jetzt sind die Messwerte auch korrekt, iterativ ist schneller als rekursiv.