# ÜB 09 Algo
unten←0;oben←n−1;
while oben > unten do
next ← ⌊ (x−A[unten])/(A[oben]−A[unten]) ⋅ (oben − unten)⌋ + unten;
if x = A[next] then
return next ;
else
n ← oben − unten + 1;
if x < A[next] then
Finde i, so dassA [next−(i+1)⋅ √n+1]≤x≤A[next−i⋅ √n];
oben ← next − i ⋅ √n;
unten←max{unten,next−(i+1)⋅ √n+1};
else
Finde i, so dassA[next+i⋅ √n]≤x≤A[next+(i+1)⋅ n−1]; oben ← min{oben, next + (i + 1) ⋅ √n − 1};
unten ← next + i ⋅ √n;
end
end
end
if oben = unten ∧ x = A[oben] then
return oben; end
return false ;

Schritt 0:\\
$E_T=\{ \}, $\\
R(1) = A \\
R(2) = B \\
R(3) = C \\
R(4) = D \\
R(5) = E \\
R(6) = F \\
R(7) = G \\
R(8) = H \\
R(9) = I \\
Elem(A)=\{ 1 \}, \\
Elem(B)=\{ 2 \}, \\
Elem(C)=\{ 3 \}, \\
Elem(D)=\{ 4 \}, \\
Elem(E)=\{ 5 \}, \\
Elem(F)=\{ 6 \}, \\
Elem(G)=\{ 7 \}, \\
Elem(H)=\{ 8 \}, \\
Elem(I)=\{ 9 \}\\

Schritt 1: \\
$E_T=\{ (1,2) \}, $\\
R(1) = B \\
R(2) = B \\
R(3) = C \\
R(4) = D \\
R(5) = E \\
R(6) = F \\
R(7) = G \\
R(8) = H \\
R(9) = I \\
Elem(B)=\{ 1, 2 \}, \\
Elem(C)=\{ 3 \}, \\
Elem(D)=\{ 4 \}, \\
Elem(E)=\{ 5 \}, \\
Elem(F)=\{ 6 \}, \\
Elem(G)=\{ 7 \}, \\
Elem(H)=\{ 8 \}, \\
Elem(I)=\{ 9 \}\\

Schritt 2: \\
$E_T=\{ (1,2), (6,8) \}, $\\
R(1) = B \\
R(2) = B \\
R(3) = C \\
R(4) = D \\
R(5) = E \\
R(6) = H \\
R(7) = G \\
R(8) = H \\
R(9) = I \\
Elem(B)=\{ 1, 2 \}, \\
Elem(C)=\{ 3 \}, \\
Elem(D)=\{ 4 \}, \\
Elem(E)=\{ 5 \}, \\
Elem(G)=\{ 7 \}, \\
Elem(H)=\{ 8, 6 \}, \\
Elem(I)=\{ 9 \}\\

Schritt 3: \\
$E_T=\{ (1,2), (6,8), (4,7) \}, $\\
R(1) = B \\
R(2) = B \\
R(3) = C \\
R(4) = G \\
R(5) = E \\
R(6) = H \\
R(7) = G \\
R(8) = H \\
R(9) = I \\
Elem(B)=\{ 1, 2 \}, \\
Elem(C)=\{ 3 \}, \\
Elem(E)=\{ 5 \}, \\
Elem(G)=\{ 7, 4 \}, \\
Elem(H)=\{ 8, 6 \}, \\
Elem(I)=\{ 9 \}\\

Schritt 4: \\
$E_T=\{ (1,2), (6,8), (4,7), (6,9)\}, $\\
R(1) = B \\
R(2) = B \\
R(3) = C \\
R(4) = G \\
R(5) = E \\
R(6) = I \\
R(7) = G \\
R(8) = I \\
R(9) = I \\
Elem(B)=\{ 1, 2 \}, \\
Elem(C)=\{ 3 \}, \\
Elem(E)=\{ 5 \}, \\
Elem(G)=\{ 7, 4 \}, \\
Elem(I)=\{ 9, 8, 6 \}\\

Schritt 5: \\
$E_T=\{ (1,2), (6,8), (4,7), (6,9), (1,4)\} $\\
R(1) = G \\
R(2) = G \\
R(3) = C \\
R(4) = G \\
R(5) = E \\
R(6) = I \\
R(7) = G \\
R(8) = I \\
R(9) = I \\
Elem(C)=\{ 3 \}, \\
Elem(E)=\{ 5 \}, \\
Elem(G)=\{ 7, 4, 1, 2 \}, \\
Elem(I)=\{ 9, 8, 6 \}\\

Schritt 6: \\
(8,9): R(8) = R(9)

Schritt 7: \\
$E_T=\{ (1,2), (6,8), (4,7), (6,9), (1,4), (3,6)\} $\\
R(1) = G \\
R(2) = G \\
R(3) = I \\
R(4) = G \\
R(5) = E \\
R(6) = I \\
R(7) = G \\
R(8) = I \\
R(9) = I \\
Elem(E)=\{ 5 \}, \\
Elem(G)=\{ 7, 4, 1, 2 \}, \\
Elem(I)=\{ 9, 8, 6, 3 \}\\

Schritt 8: \\
$E_T=\{ (1,2), (6,8), (4,7), (6,9), (1,4), (3,6), (7,8) \} $\\
R(1) = I \\
R(2) = I \\
R(3) = I \\
R(4) = I \\
R(5) = E \\
R(6) = I \\
R(7) = I \\
R(8) = I \\
R(9) = I \\
Elem(E)=\{ 5 \}, \\
Elem(I)=\{ 9, 8, 6, 3, 7, 4, 1, 2 \}\\

Schritt 9: \\
(2,3): R(2) = R(3)

Schritt 10: \\
(2,6): R(2) = R(6)

Schritt 11: \\
$E_T=\{ (1,2), (6,8), (4,7), (6,9), (1,4), (3,6), (7,8), (2, 5) \} $\\
R(1) = I \\
R(2) = I \\
R(3) = I \\
R(4) = I \\
R(5) = I \\
R(6) = I \\
R(7) = I \\
R(8) = I \\
R(9) = I \\
Elem(I)=\{ 9, 8, 6, 3, 7, 4, 1, 2, 5 \}\\

Schritt 12: \\
(5, 8): R(5) = R (8)

Schritt 13: \\
(1, 5): R(1) = R (5)

Schritt 14: \\
(5,7): R(5) = R (7)

Schritt 15: \\
(2, 5): R(2) = R (5)

Schritt 16: \\
(5, 6): R(5) = R (6)

-------

\begin{table}[]
\begin{tabular}{llll}
Schritt 0: & Schritt 1: & Schritt 2: & Schritt 3: \\
$E_T=\{ \}, $ & $E_T=\{ (1,2) \}, $ & $E_T=\{ (1,2), (6,8) \}, $ & $E_T=\{ (1,2), (6,8), (4,7) \}, $ \\
R(1) = A & R(1) = B & R(1) = B & R(1) = B \\
R(2) = B & R(2) = B & R(2) = B & R(2) = B \\
R(3) = C & R(3) = C & R(3) = C & R(3) = C \\
R(4) = D & R(4) = D & R(4) = D & R(4) = G \\
R(5) = E & R(5) = E & R(5) = E & R(5) = E \\
R(6) = F & R(6) = F & R(6) = H & R(6) = H \\
R(7) = G & R(7) = G & R(7) = G & R(7) = G \\
R(8) = H & R(8) = H & R(8) = H & R(8) = H \\
R(9) = I & R(9) = I & R(9) = I & R(9) = I \\
Elem(A)=\{ 1 \}, & Elem(B)=\{ 1, 2 \}, & Elem(B)=\{ 1, 2 \}, & Elem(B)=\{ 1, 2 \}, \\
Elem(B)=\{ 2 \}, & Elem(C)=\{ 3 \}, & Elem(C)=\{ 3 \}, & Elem(C)=\{ 3 \}, \\
Elem(C)=\{ 3 \}, & Elem(D)=\{ 4 \}, & Elem(D)=\{ 4 \}, & Elem(E)=\{ 5 \}, \\
Elem(D)=\{ 4 \}, & Elem(E)=\{ 5 \}, & Elem(E)=\{ 5 \}, & Elem(G)=\{ 7, 4 \}, \\
Elem(E)=\{ 5 \}, & Elem(F)=\{ 6 \}, & Elem(G)=\{ 7 \}, & Elem(H)=\{ 8, 6 \}, \\
Elem(F)=\{ 6 \}, & Elem(G)=\{ 7 \}, & Elem(H)=\{ 8, 6 \}, & Elem(I)=\{ 9 \} \\
Elem(G)=\{ 7 \}, & Elem(H)=\{ 8 \}, & Elem(I)=\{ 9 \} & \\
Elem(H)=\{ 8 \}, & Elem(I)=\{ 9 \} & & \\
Elem(I)=\{ 9 \} & & &
\end{tabular}
\end{table}

\begin{table}[]
\begin{tabular}{lll}
Schritt 4: & Schritt 5: & Schritt 6: \\
$E_T=\{ (1,2), (6,8), (4,7), (6,9)\}, $ & $E_T=\{ (1,2), (6,8), (4,7), (6,9), (1,4)\} $ & (8,9): R(8) = R(9) \\
R(1) = B & R(1) = G & \\
R(2) = B & R(2) = G & \\
R(3) = C & R(3) = C & \\
R(4) = G & R(4) = G & \\
R(5) = E & R(5) = E & \\
R(6) = I & R(6) = I & \\
R(7) = G & R(7) = G & \\
R(8) = I & R(8) = I & \\
R(9) = I & R(9) = I & \\
Elem(B)=\{ 1, 2 \}, & Elem(C)=\{ 3 \}, & \\
Elem(C)=\{ 3 \}, & Elem(E)=\{ 5 \}, & \\
Elem(E)=\{ 5 \}, & Elem(G)=\{ 7, 4, 1, 2 \}, & \\
Elem(G)=\{ 7, 4 \}, & Elem(I)=\{ 9, 8, 6 \} & \\
Elem(I)=\{ 9, 8, 6 \} & &
\end{tabular}
\end{table}

\begin{table}[]
\begin{tabular}{ll}
Schritt 8: & Schritt 9: \\
$E_T=\{ (1,2), (6,8), (4,7), (6,9), (1,4), (3,6), (7,8) \} $ & (2,3): R(2) = R(3) \\
R(1) = I & Schritt 10: \\
R(2) = I & (2,6): R(2) = R(6)\\
R(3) = I & \\
R(4) = I & \\
R(5) = E & \\
R(6) = I & \\
R(7) = I & \\
R(8) = I & \\
R(9) = I & \\
Elem(E)=\{ 5 \}, & \\
Elem(I)=\{ 9, 8, 6, 3, 7, 4, 1, 2 \} &
\end{tabular}
\end{table}

\begin{table}[]
\begin{tabular}{lll}
Schritt 11: & Schritt 12: & \\
$E_T=\{ (1,2), (6,8), (4,7), (6,9), (1,4), (3,6), (7,8), (2, 5) \} $ & (5, 8): R(5) = R (8) & \\
R(1) = I & Schritt 13: & \\
R(2) = I & (1, 5): R(1) = R (5) & \\
R(3) = I & Schritt 14: & \\
R(4) = I & (5,7): R(5) = R (7) & \\
R(5) = I & Schritt 15: & \\
R(6) = I & (2, 5): R(2) = R (5) & \\
R(7) = I & Schritt 16: & \\
R(8) = I & (5, 6): R(5) = R (6) & \\
R(9) = I & & \\
Elem(I)=\{ 9, 8, 6, 3, 7, 4, 1, 2, 5 \} & &
\end{tabular}
\end{table}