Genau das habe ich ja oben beschrieben.
Bei deiner Implementation muss immer bis zum Treffer durchgelaufen werden, also etwa n/2 Vergleiche angestellt werden. (Wenn man nichts über die Verteilung weiss)
Wenn man jetzt wie bei meiner Beschreibung statt p(x=n) sondern p(x<=n) in die Liste schreibt, könnte man z.b. in der Mitte anfangen und sich dann in die passende Richtung fortbewegen, was dann auf n/4 Vergleiche (/pm 1) kommt.
Wann so eine Zahl häufiger gesucht ist, sollte man den Zahlenstrahl so umordnen, dass zuerst die großen Felder kommen, so dass durchschnittlich unter n/2 Vergleiche stattfinden.
// zum neuen Beitrag von Hagen:
Dabei gehst du aber aus, dass alles glatt aufgeht. Die Verteilung für 6 Zahlen und p(1)=0.12 und p(2)=...=p(6) kann man damit nicht schön modellieren.