\documentclass{bschlangaul-aufgabe}
\bLadePakete{java,tabelle}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 3},
  Thematik = {Code-Inspection bei Binärer Suche},
  Referenz = 66116-2017-H.T1-TA2-A4,
  RelativerPfad = Examen/66116/2017/09/Thema-1/Teilaufgabe-2/Aufgabe-4.tex,
  ZitatSchluessel = sosy:ab:9,
  ZitatBeschreibung = {Aufgabe 3},
  BearbeitungsStand = mit Lösung,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Binäre Suche, Design by Contract, Kontrollflussgraph, Vollständige Anweisungsüberdeckung},
  EinzelpruefungsNr = 66116,
  Jahr = 2017,
  Monat = 09,
  ThemaNr = 1,
  TeilaufgabeNr = 2,
  AufgabeNr = 4,
}

Die\footcite[Aufgabe 3]{sosy:ab:9} folgende Seite enthält
Software-Quellcode, der einen Algorithmus zur binären Suche\index{Binäre
Suche} implementiert. Dieser ist durch Inspektion zu überprüfen. Im
Folgenden sind die Regeln der Inspektion angegeben.
\footcite[Thema 1 Teilaufgabe 2 Aufgabe 4]{examen:66116:2017:09}

\bigskip

\noindent
\begin{tabularx}{\linewidth}{|l|l|X|}
\hline
RM1 &
(Dokumentation) &
Jede Quellcode-Datei beginnt mit einem Kommentar, der den Klassennamen,
Versionsinformationen, Datum und Urheberrechtsangaben enthält.

\\\hline

RM2 &
(Dokumentation) &
Jede Methode wird kommentiert. Der Kommentar enthält eine vollständige
Beschreibung der Signatur so wie eine
Design-by-Contract-Spezifikation\index{Design by Contract}.

\\\hline

RM3 &
(Dokumentation) &
Deklarationen von Variablen werden kommentiert.
\\\hline

RM4 &
(Dokumentation) &
Jede Kontrollstruktur wird kommentiert.
\\\hline

RM5 &
(Formatierung) &
Zwischen einem Schlüsselwort und einer Klammer steht
ein Leerzeichen.
\\\hline

RM6 &
(Formatierung) &
Zwischen binären Operatoren und den Operanden stehen
Leerzeichen.
\\\hline

RM7 &
(Programmierung) &
Variablen werden in der Anweisung initialisiert, in der sie
auch deklariert werden.
\\\hline

RM8 &
(Bezeichner) &
Klassennamen werden groß geschrieben, Variablennamen klein.
\\\hline
\end{tabularx}

%-----------------------------------------------------------------------
%
%-----------------------------------------------------------------------

\bigskip

% Datei kann nicht in das Java-Repository eingebundne werden, weil
% javadoc dann sehr viele Dokumentationsfehler meldet

% \bJavaExamen{66116}{2017}{09}{BinarySearch}

\begin{bJavaAngabe}
/**
 * BinarySearch.java
 *
 * Eine Implementierung der ”Binaere Suche”
 * mit einem iterativen Algorithmus
 */
class BinarySearch {

  /**
   * BinaereSuche
   * a: Eingabefeld
   * item: zusuchendesElement
   * returnValue: der Index des zu suchenden Elements oder -1
   *
   * Vorbedingung:
   * a.length > 0
   * a ist ein linear geordnetes Feld:
   * For all k: (1 <= k < a.length) ==> (a[k−1] <=a [k])
   *
   * Nachbedingung:
   * Wenn item in a, dann gibt es ein k mit a[k] == item und returnValue == k
   * Genau dann wenn returnValue == −1 gibt es kein k mit 0 <= k < a.length
   * und a[k]==item.
   */
  public static int binarySearch(float a[], float item) {

    int End;  // exklusiver Index fuer das Ende des
              // zudurchsuchenden Teils des Arrays
    int start = 1; // inklusiver Index fuer den Anfang der Suche
    End = a.length;

    // Die Schleife wird verlassen, wenn keine der beiden Haelften das
    // Element enthaelt.
    while(start < End) {

      // Teilung des Arrays in zwei Haelften
      // untere Haelfte: [0,mid[
      // obere Haelfte: ]mid,End[
      int mid = (start + End) / 2;

      if (item > a[mid]) {
        // Ausschluss der oberen Haelfte
        start = mid + 1;
      } else if(item < a[mid]) {
        // Ausschluss der unteren Haelfte
        End = mid-1;
      } else {
        // Das gesuchte Element wird zurueckgegeben
        return (mid);
      }
    } // end of while

    // Bei Misserfolg der Suche wird −1 zurueckgegeben
    return (-1);
  }
}
\end{bJavaAngabe}

\begin{enumerate}

%%
%
%%

\item Überprüfen Sie durch Inspektion, ob die obigen Regeln für den
Quellcode eingehalten wurden. Erstellen Sie eine Liste mit allen
Verletzungen der Regeln. Geben Sie für jede Verletzung einer Regel die
Zeilennummer, Regelnummer und Kommentar an, \zB (07, RM4, while nicht
kommentiert). Schreiben Sie nicht in den Quellcode.

\begin{bAntwort}
\noindent
\begin{tabularx}{\linewidth}{|l|l|X|}
\hline
Zeile & Regel & Kommentar\\\hline\hline

3-8 & RM1 &
Fehlen von Versionsinformationen, Datum und Urheberrechtsangaben \\\hline

11-26 & RM2 &
Fehlen der Invariante in der Design-by-Contract-Spezifikation \\\hline

36,46 & RM5 & Fehlen des Leerzeichens vor der Klammer \\\hline

48 & RM6 &

Um einen binären (zweistellige) Operator handelt es sich im
Code-Beispiel um den Subtraktionsoperator: \bJavaCode{mid-1}. Hier
fehlen die geforderten Leerzeichen. \\\hline

32 & RM7 &

Die Variable \bJavaCode{End} wird in Zeile 32 deklariert, aber erst in
Zeile initialisiert \bJavaCode{End = a.length;} \\\hline

32 & RM8 &
Die Variable \bJavaCode{End} muss klein geschrieben werden. \\\hline
\end{tabularx}

\end{bAntwort}

%%
%
%%

\item Entspricht die Methode \bJavaCode{binarySearch} ihrer Spezifikation,
die durch Vor-und Nachbedingungen angeben ist? Geben Sie gegebenenfalls
Korrekturen der Methode an.

\begin{bAntwort}
\bPseudoUeberschrift{Korrektur der Vorbedingung}

Die Vorbedingung ist nicht erfüllt, da weder die Länge des Feldes
\bJavaCode{a} noch die Reihenfolge der Feldeinträge geprüft wurden.

\begin{bJavaAngabe}
if (a.length <= 0) {
  return -1;
}

for (int i = 0; i < a.length; i ++) {
  if ( a[i] > a[i + 1]) {
    return -1;
  }
}
\end{bJavaAngabe}

\bPseudoUeberschrift{Korrektur der Nachbedingung}

\bJavaCode{int start} muss mit \bJavaCode{0} initialisiert werden, da sonst
\bJavaCode{a[0]} vernachlässigt wird.
\end{bAntwort}

%%
%
%%

\item Beschreiben alle Kommentare ab Zeile 24 die Semantik des Codes
korrekt? Geben Sie zu jedem falschen Kommentar einen korrigierten
Kommentar mit Zeilennummer an.

\begin{bAntwort}
\begin{tabularx}{\linewidth}{lXX}
Zeile & Kommentar im Code & Korrektur \\

34-35 &
\bJavaCode{// Die Schleife wird verlassen, wenn keine der beiden Haelften das
Element enthaelt.} &
\bJavaCode{// Die Schleife wird verlassen, wenn keine der beiden Haelften das
Element enthaelt oder das Element gefunden wurde.} \\

44 &
\bJavaCode{// Ausschluss der oberen Haelfte} &
\bJavaCode{// Ausschluss der unteren Haelfte} \\

47 &
\bJavaCode{// Ausschluss der unteren Haelfte} &
\bJavaCode{// Ausschluss der oberen Haelfte} \\

50 &
\bJavaCode{// Das gesuchte Element wird zurueckgegeben} &
\bJavaCode{// Der Index des gesuchten Elements wird zurueckgegeben} \\

\end{tabularx}
\end{bAntwort}

%%
%
%%

\item Geben Sie den Kontrollflussgraphen\index{Kontrollflussgraph} für
die Methode \bJavaCode{binarySearch} an.

%%
%
%%

\item Geben Sie maximal drei Testfälle für die Methode
\bJavaCode{binarySearch} an, die insgesamt eine vollständige
Anweisungsüberdeckung\index{Vollständige Anweisungsüberdeckung} leisten.

\begin{bAntwort}
Die gegebene Methode: \bJavaCode{binarySearch(a[], item)}

\bPseudoUeberschrift{Testfall}

\begin{enumerate}
\item Testfall: \bJavaCode{a[] = {1, 2, 3}, item = 4}
\item Testfall: \bJavaCode{a[] = {1, 2, 3}, item = 2}
\end{enumerate}
\end{bAntwort}
\end{enumerate}
\end{document}