Aufgabe:
Sei \( n \in \mathbb{N} \) und \( d=2^{n}-1 \). Gegeben sei eine Liste \( \left(x_{1}, \ldots, x_{d}\right) \) geordneter Größen \( x_{1}< \) \( \cdots<x_{d} \). Gesucht wird die Position eines Elements \( y \) der Liste. Dazu wird der folgende Algorithmus verwendet:
Vergleiche \( y \) mit dem mittleren Eintrag \( x_{\frac{d+1}{2}} \) der Liste \( \left(x_{1}, \ldots, x_{d}\right) \). Gilt \( y=x_{\frac{d+1}{2}} \), so ist die Position bestimmt (Position \( \frac{d+1}{2} \) ) und der Algorithmus bricht ab. Gilt \( y<x_{\frac{d+1}{2}}^{2} \), so bilde die Liste \( \left(x_{1}, \ldots, x_{\frac{d-1}{2}}\right) \) aller Einträge kleiner als \( x_{\frac{d+1}{2}} \) und wiederhole den AlgorithmusSchritt mit dieser Liste. Gilt \( y>x_{\frac{d+1}{2}} \), so bilde die Liste \( \left(x_{\frac{d+3}{2}}, \ldots, x_{d}\right) \) aller Einträge größer als \( x_{\frac{d+1}{2}} \) und wiederhole den Algorithmus-Schritt mit dieser Liste.
Dieser Schritt wird so lange wiederholt, bis die Position von \( y \) bestimmt ist, d.h. bis der Algorithmus von sich aus abbricht.
Nehmen Sie an, dass die Position des gesuchten Wertes y zufällig (gleichverteilt) in der Liste auftritt. Die Zufallsvariable \( N \) gebe die Anzahl der Schritte an, die der Algorithmus braucht, um \( y \) zu finden.
a) Geben Sie die maximale Anzahl von Schritten von \( N \) an.
b) Bestimmen Sie die Verteilung und die Verteilungsfunktion \( F_{N} \) der Zufallsvariablen \( N \).
Ich glaube das Algorithmus ist Binäre Suche
