// Binäre Suche
class BinSearch {

    // Zeitbedarf des Algorithmus:
    // Beobachtung: nach k Schleifendurchlauefen
    // sind von ug..og noch a.length/(2 ^ k) 
    // Array-Elemente vorhanden, die ggf. den
    // gesuchten Wert enthalten können.
    //  k = 1:  a.length / 2
    //  k = 2:  a.length / (2^2) ...
    //
    // Algorithmus terminiert bei
    // a.length/(2 ^ k) <= 1 also
    //  k = log_2(n),
    // also ist dies der Zeitbedarf im schlimmsten Fall.
    // 
    public static int binSearch(int x, int[] a) {
	int i = -1;

	int ug; // Untergrenze
	int og; // Obergrenze
	int m; // Mittlerer Index

	ug = 0;
	og = a.length - 1;

        // Arbeitsweise des Algorithmus: 
        // ug, og werden immer so
        // modifiziert, dass x entweder NICHT
        // in a liegt oder im Bereich a[ug]..a[og].
        //
        // Wenn der gesuchte Wert x nicht mit a[m]
        // übereinstimmt, kann x nur
        //    - in a[m+1]..a[og] liegen, falls a[m] < x
        //    - in a[ug]..a[m-1] liegen, falls a[m] > x
        // Dementsprechend wird im ersten Fall die Untergrenze
        // auf m+1 gesetzt, im zweiten Fall die Obergrenze
        // auf m-1 gesetzt.
        // 
        // Da, falls x nicht mit a[m] übereinstimmt, immer der
        // Abstand zwischen Unter- und Obergrenze um mindestens
        // 1 verkleinert wird, garantiert die Schleifenbedingung
        // ug <= og die Terminierung, falls x nicht im Array liegt.
 

	do { 

	    m = (og + ug)/2;

	    if ( a[m] == x ) {
		i = m;
	    }
	    else if ( a[m] < x ) {
		ug = m + 1;
	    }
	    else {
		og = m - 1;
	    }

	} while ( i == -1 && ug <= og );

	return i;

    }


    // Der einfachst mögliche Algorithmus, um im 
    // Back-to-Back Test zu prüfen, ob x in a liegt:
    // Lineare Suche im Array (Zeitaufwand a.length
    // im schlimmsten Fall).
    public static boolean isInA(int x, int[] a) {

	for ( int i = 0; i < a.length; i++ ) {
	    if ( a[i] == x ) return true;
	}
	return false;

    }


    public static void main(String[] args) {

	int a[] = { 1, 15, 21,21, 22, 23, 29, 
                    100, 101, 101, 102, 103};
	int idx;
	boolean failed = false;

        // Spezifikation der Methode binSearch(x,a): 
        // Rückgabewert idx = -1 falls x nicht in a[]
        //       idx in 0..a.length-1, falls a[idx] == x

        // Beobachtung: Weil a sortiert ist, folgt
        // aus x < a[i]: x ist NICHT in a[] oder 
        //               x ist in a[0]..a[i-1]


        // Test von binSearch():
        // Wähle Zahlen x zum Suchen in a[] aus dem 
        // Bereich -110..110. Damit ist garantiert,
        // dass sowohl Elemente x gesucht werden, die
        // nicht in a liegen, als auch welche, die in a
        // liegen. Weiterhin erfolgen auch Grenzwerttests,
        // denn es wird auch nach dem ersten und dem letzten
        // Element von a gesucht.
	for ( int x = -110; x <= 110; x++ ) {
	    idx = binSearch(x,a);
  
            // Für den Fall, dass 0 <= idx zurückgegeben wird,
            // können wir direkt nachprüfen, ob ein korrekter
            // Index gefunden wurde: Ein Fehler liegt vor,
            // wenn x != a[idx] ist oder wenn das Programm
            // mit einer out-of-range Exception (illegaler 
            // Array Index) abstürzt.
	    if ( 0 <= idx && a[idx] != x ) {
		System.out.println("FAILED: x = " + 
                            x + " != a[ " + idx + "]");
		failed = true;
	    }            
            // Bei Rückgabewert idx = -1 muss geprüft werden,
            // ob x wirklich nicht im Array vorhanden ist.
            // Dies erfolgt durch einen Back-to-back Test 
            // mit einem 2. Algorithmus, implementiert
            // durch Methode isInA(x,a): Wenn diese auch anzeigt, 
            // dass x nicht in a ist, vertrauen wir darauf, dass
            // die Wahrscheinlichkeit dafür, dass beide Implementierungen 
            // im selben Fall fehlerhaft -1 zurückgeben, vernachlässigt
            // werden kann. Falls isInA(x,a) == true aber binSearch(x,a) < 0, 
            // muss analysiert werden, ob der Fehler im Testling binSearch()
            // oder in der Back-to-Back Methode isInA() liegt.
	    if ( idx == -1 && isInA(x,a) ) {
		System.out.println("FAILED: x = " + x + 
                                   " result = " + idx);
		failed = true;
	    }

	}

        // Gesamtergebnis des Tests:
	if ( failed )
	    System.out.println("FAILED.");
	else 
 	    System.out.println("PASSED.");


    }

}