---
# System prepended metadata

title: ÜB 09 Algo

---

# Ü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}



