Einsendung:Lösungsvorschlag für findIndexHi Volkard! Das ist gut. Manchmal braucht man eben doch globale Variablen. Es scheint eigentlich zu funktionieren, jedoch bin ich mir noch nicht sicher, ob dieses jetzt wirklich die schnellstmöglichste und beste Umsetzung des binären Suchens ist. Es ist IMHO die schnellste. Auf jeden Fall ist mir aufgefallen, daß Zahlen, die weiter oben im Index liegen, meist mehr (bei mein Testläufen war das nur einer) Durchläufe benötigen. Das liegt an den Stellen (zwei an der Zahl), an denen ich die mitte erzeuge. Denn wenn ich eine Mitte aus zwei Zahlen ermittle, dessen Differenz ungerade ist wie z.B. 10 und 5 dann nimmt die mitte immer den kleineren Wert an. Also in meinen Beispiel 7. Aber dafür gibt es wohl keine Lösung, oder? Ich glaube, es gibt keine Lösung. 0 2 1 2 2 2 3 2 4 2 5 2 6 3 7 4 8 4 9 4 summe 27 Die Verteilung ist sehr asymmetrisch. Das liegt wohl an
Ich verstehe das
nicht. Mit
werden die Suchzeiten zu 0 3 1 3 2 3 3 2 4 2 5 2 6 2 7 3 8 3 9 3 summe 26 Für bessere Messergebnisse lasse ich auch die Summen für 1000000 Zahlen berechnen:
Für andere Messergebnisse lasse ich auch die Summen für 5000000 Zahlen berechnen:
Die beiden Zeilen sind also als gleich schnell zu erachten. Da dies eine etwas anspruchsvolle Aufgabe war und ich schon einige Zeit damit verbracht habe, würde ich natürlich gerne Wissen ob es denn nun die richtige Lösung ist. Sie ist genau richtig. Und die Aufgabe war so anspruchsvoll, daß es drei Monate gedauert hat, bis die erste Lösung (nämlich diese hier) eingegangen ist.
Das ergibt dann:
Falls Ihnen Fehler im Text auffallen oder Sie Verbesserungsvorschläge haben, dann schicken Sie mir bitte eine Mail. Ich werde mich dann sofort darum kümmern. [aktuelle Version] [inhalt] [index] [Fehlerkorrektur, Verbesserungsvorschlag] © Volkard Henkel <volkard@normannia.de>, last update: 08/25/00 |