\documentclass{bschlangaul-aufgabe}
\bLadePakete{java}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 5},
  Thematik = {Schnelle Suche von Schlüsseln: odd-ascending-even-descending-Folge},
  Referenz = 66115-2020-H.T2-TA2-A5,
  RelativerPfad = Examen/66115/2020/09/Thema-2/Teilaufgabe-2/Aufgabe-5.tex,
  ZitatSchluessel = examen:66115:2020:09,
  BearbeitungsStand = mit Lösung,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Binäre Suche},
  EinzelpruefungsNr = 66115,
  Jahr = 2020,
  Monat = 09,
  ThemaNr = 2,
  TeilaufgabeNr = 2,
  AufgabeNr = 5,
}

\let\j=\bJavaCode

Eine Folge von Zahlen ist eine
\emph{odd-ascending-even-descending}-Folge, wenn gilt:
\index{Binäre Suche}
\footcite{examen:66115:2020:09}
\begin{quote}
Zunächst enthält die Folge alle Schlüssel, die \emph{ungerade} Zahlen
sind, und diese Schlüssel sind aufsteigend sortiert angeordnet. Im
Anschluss daran enthält die Folge alle Schlüssel, die \emph{gerade}
Zahlen sind, und diese Schlüssel sind absteigend sortiert angeordnet.
\end{quote}

\begin{enumerate}
\item Geben Sie die Zahlen $10, 3, 11, 20, 8, 4, 9$ als
\emph{odd-ascending-even-descending}-Folge an.

\begin{bAntwort}
$3, 9, 11, 20, 10, 8, 4$
\end{bAntwort}

\item Geben Sie einen Algorithmus (\zB in Pseudocode oder Java) an,
der für eine \emph{odd-ascending-even-descending}-Folge $F$ gegeben als
Feld und einem Schlüsselwert $S$ prüft, ob $S$ in $F$ vorkommt und
\bJavaCode{true} im Erfolgsfall und ansonsten \bJavaCode{false}
liefert. Dabei soll der Algorithmus im Worst-Case eine echt bessere
Laufzeit als Linearzeit (in der Größe der Arrays) haben. Erläutern Sie
Ihren Algorithmus und begründen Sie die Korrektheit.

\begin{bAntwort}
Bei dem Algorithmus handelt es sich um einen leicht abgewandelten Code,
der eine „klassische“ binären Suche implementiert.

\bJavaExamen[firstline=5,lastline=26]{66115}{2020}{09}{UngeradeGerade}
\end{bAntwort}

%%
% c)
%%

\item Erläutern Sie schrittweise den Ablauf Ihres Algorithmus für die
Folge $1, 5, 11, 8, 4, 2$ und
den Suchschlüssel $4$.

\begin{bAntwort}

Die erste Zeile der Methode \j{suche} initialisiert die Variable
\j{links} mit 0 und \j{rechts} mit 5. Da \j{links} kleiner ist als
\j{rechts}, wird die \j{while}-Schleife betreten und die Variable
\j{mitte} auf 2 gesetzt. Da der gesuchte Schlüssel gerade ist und
\j{feld[2]} 11 ist, also größer, wird in den \j{true}-Block der
\j{if}-Bedingung besprungen und die Variable \j{links} aus 3 gesetzt.

Zu Beginn des 2. Durchlaufs der \j{while}-Schleife ergeben sich folgende
Werte: \j{links}: 3 \j{mitte}: 4 \j{rechts}: 5.

In der anschließenden Bedingten Anweisung wird die \j{while}-Schleife
verlassen und \j{true} zurückgegeben, da mit \j{feld[4]} der gewünschte
Schlüssel gefunden wurde.
\end{bAntwort}

%%
% d)
%%

\item Analysieren Sie die Laufzeit Ihres Algorithmus für den Worst-Case,
geben Sie diese in $\mathcal{O}$-Notation an und begründen Sie diese.

\begin{bAntwort}
Die Laufzeit des Algorithmuses ist in der Ordnung $\mathcal{O}(\log_2
n)$.

Im schlechtesten Fall muss nicht die gesamte Folge durchsucht werden.
Nach dem ersten Teilen der Folge bleiben nur noch $\frac{n}{2}$
Elemente, nach dem zweiten Schritt $\frac{n}{4}$, nach dem dritten
$\frac{n}{8}$ usw. Allgemein bedeutet dies, dass im $i$-ten Durchlauf
maximal $\frac{n}{2^i}$ Elemente zu durchsuchen sind. Entsprechend
werden $\log_2 n$ Schritte benötigt.
\end{bAntwort}

\bPseudoUeberschrift{Kompletter Code}

\bJavaExamen{66115}{2020}{09}{UngeradeGerade}

\bPseudoUeberschrift{Test-Code}

\bJavaTestDatei{examen/examen_66115/jahr_2020/herbst/UngeradeGeradeTest}

\end{enumerate}
\end{document}