ThomasK Da fehlt die eins. Es sind log2 (n+1) Versuche, also nicht 8, sondern 9!
Meiner Meinung sind es 8.
Bei einer "echten" binären Suche muss man nochmal den Endwert testen, hier aber nicht. Mini-Beispiel: Du willst wissen, ob die Grenze bei 1 Euro oder bei 2 Euro liegt. Da reicht ein Versuch (egal ob 1 oder 2), da wir wissen, dass die Grenze existiert. Ist 1 erfolglos, dann ist eben die Grenze 2, das muss man nicht nochmals überprüfen. Die Information "Grenze existiert" spart einen Versuch. Eben den letzten, der bei einer Suche in einem Binärbaum erforderlich ist, weil man ja nicht weiß, was da für ein Datenwert in dem Blatt steht. Ich hoffe das stimmt, denn 4 Testwerte brauchen dann 2 Versuche, 8 - 4, 16 - 5, 32 - 6, 64 - 7, 128 - 8. Und wir hatten doch nur 127 Werte. Aber vielleicht schreibe ich auch Unsinn, dann diskutieren wir im Off-Topic weiter. 
