package Sortieralgorithmen;

public class BinarySearch {
    // Implementierung nach Vorlesung WS 16/17
    public static int find ( int [] a, int x) { 
        return find0(a, x, 0, a.length-1) ; 
    }
    // Finde x in a im Bereich von n1 bis n2 (jeweils inkl.)
    public static int find0(int[] a, int x, int n1, int n2) {
        int t = (n1 + n2) / 2;              // Vergleichselement im aktuellen Bereich
        if (a[t] == x)                      // Element wurde gefunden
            return t;                       //  -> Index zurückgeben
        else if (n1 == n2)                  // Grenzen gleich (-> nur ein Element)
            return -1;                      //  -> nicht gefunden
        else if (x > a[t])                  // x liegt rechts vom Vergleichselement
            return find0(a, x, t+1, n2);    //  -> rechts weitersuchen (t+1 bis n2)
        else if (n1 < t)                    // sonst (nur wenn der linke Bereich überhaupt existiert und nicht t==n1 gilt)
            return find0(a, x, n1, t-1);    //  -> links weitersuchen (n1 bis t-1)
        else 
            return -1;                      // nicht gefunden
    }

    
    // WS 12/13 Wiederholung
    static boolean findRec(int[] values, int elt, int left, int right) {
        if (left > right)
            return false;
        
        int pivotIndex = (left + right) / 2;
        if (values[pivotIndex] == elt)
            return true;
        else if (values[pivotIndex] > elt)
            return findRec(values, elt, left, pivotIndex - 1);
        else if (values[pivotIndex] < elt)
            return findRec(values, elt, pivotIndex + 1, right);
        
        return false;
    }
}