import java.util.Random;
/**
 * Die Klasse Suchen enthält einfache Suchverfahren.
 * 
 * @author MB
 * @version JUN 2014
 */
public class Suchen
{
   
    
    
    
    /**
     *  Sequentielle Suche sucht eine Zahl in einem Array von der Startposition bis zur Endposition.
     *  Laufzeit: n.
     *  @param a - das zu durchsuchende Array
     *  @param gesucht - der gesuchte Zahlenwert
     *  @param startposition - die Position, ab der gesucht wird (i.d.R. 0)
     *  @param endposition - die Position, bis zu der gesucht wird (i.d.R. a.length-1)
     *  @return - die Position, an der sich die Zahl befindet, ansonsten -1
     */
    public static int sequentielleSuche(long[] a, int gesucht, int startposition, int endposition){
        int i = 0;
        for(i = startposition; i <= endposition; i++){
            if(a[i] == gesucht){
                return i;
            }
        }
        return -1;
    }
    
    /**
     *  gibt den Maximalwert zurueck
     */
    public static long sequentiellesMaximum(long[] a){
        int i = 0;
        long max = a[0];
        for(i = 1; i < a.length; i++){
            if(a[i] > max){
                max = a[i];
            }
        }
        return max;
    } 
    
    /**
     * gibt die Position, an der sich der Maximalwert befindet
     */
    public static int sequentiellesMaximumPosition(long[] a){
        int i = 0;
        int pos = 0;
        long max = a[0];
        for(i = 1; i < a.length; i++){
            if(a[i] > max){
                max = a[i];
                pos = i;
            }
        }
        return pos;
    } 
    
    /**
     *  Binäre Suche sucht eine Zahl in einem sortierten Array von der Startposition bis zur Endposition
     *  durch wiederholte Eingrenzung des Suchbereiches. Laufzeit: log n.
     *  @param a - das zu durchsuchende Array
     *  @param gesucht - der gesuchte Wert
     *  @param startposition - die Position, ab der gesucht wird (i.d.R. 0)
     *  @param endposition - die Position, bis zu der gesucht wird (i.d.R. a.length-1)
     *  @return - die Position, an der sich die Zahl befindet, ansonsten -1
     */
    public static int binaereSuche(Object[] a, Object gesucht, int startposition, int endposition){
        while(endposition >= startposition){
            int m = (startposition + endposition)/2;
            if( gesucht == a[m]){
                return m;
            }
            if (!((gesucht instanceof Comparable) && (a[m] instanceof Comparable))){
                System.err.println("Das Vergleichsobjekt unterstützt keine Vergleichsoperationen");
                return -1;
            }
            Comparable c = (Comparable) gesucht;
            if ( c.compareTo(a[m]) > 0){
                endposition = m - 1;
            }
            else {
                startposition = m + 1;
            }
        }
        return -1;
    }
    
    /**
     * spezielle binaere Suche fuer [long]-Arrays; in Java vordefiniert: Arrays.binarySearch(XXX[] array, XXX suchwert)
     * @param endposition - immer kuerzer als das Array: maximal a.length-1
     */
    public static int[] binaereSuche(long[] a, long gesucht, int startposition, int endposition){
        int[] out = new int[2];
        int counter = 0;
        while(endposition >= startposition){
            int m = (startposition + endposition)/2;
            if( gesucht == a[m]){
                out[0] = m;
                out[1] = counter;
                return out;
            }
            if ( gesucht > a[m]){
                startposition = m + 1;
            }
            else {
                endposition = m - 1;
            }
            counter++;
        }
        out[0] = -1;
        out[1] = counter;
        return out;
    }
    
    /**
     *  Suche nach dem Maximum in einem Array durch Divide & Conquer 
     *  (rekursiv, aber in diesem Fall nicht effektiver, da doch alle Zahlen 
     *  einmal mit einer anderen verglichen werden muessen, wie dies in anderer 
     *  Form auch in der sequentiellen Suche nach dem Maximum geschieht, wobei hier
     *  die Vergleiche der relativen Maxima der Teillisten hinzukommen).
     *  Vorausgesetzt wird keine besondere Anordnung der Elemente.
     */
    public static long rekursivesMaximum(long[] a, int links, int rechts){
        if(rechts - links < 1){
            return a[links];
        }
        int m = (links + rechts) / 2;
        long l = rekursivesMaximum(a,links,m);
        long r = 0;
        if (m+1 < a.length){
            r = rekursivesMaximum(a,m+1,rechts);
        }
        else{
            r = a[a.length-1];
        }
        if(l > r){
            return l;
        }
        else {
            return r;
        }
    }
    
    /**
     * Interpolationssuche, die beim Start der Suche eine ungefaehre Normalverteilung (von Zahlen) animmt.
     * Dadurch wird die binaere Suche von vorneherein auf einen Zielbereich fokussiert.
     */
    public static int[] interpolationssuche(long[] a, long gesucht){
        int[] out = new int[2];
        int counter = 0;
        int startposition = 0;
        int endposition = a.length-1;
        int m = (int) gesucht; // getippter Startwert bei voelliger Gleichverteilung
        while(endposition >= startposition){
            if( gesucht == a[m]){
                out[0] = m;
                out[1] = counter;
                return out;
            }
            if (gesucht > a[m]){
                startposition = m + 1;
            }
            else {
                endposition = m - 1;
            }
            m = (startposition+endposition)/2;
            counter++;
        }
        out[0] = -1;
        out[1] = counter;
        return out;
    }
    
    /**
     * bereichsinterpolationssuche geht davon aus, dass die Werte in einem Array mehr oder weniger gleich verteilt sind,
     * und arbeitet sich so in Einerschritten von der Startposition aus vorwaerts
     */
    public static int[] bereichsinterpolationssuche(long[] a, long gesucht){
        int[] out = new int[2];
        int counter = 0;
        int m = (int) gesucht; // getippter Startwert bei voelliger Gleichverteilung
        while((m >= 0) && (m < a.length)){
            if( gesucht == a[m]){
                out[0] = m;
                out[1] = counter;
                return out;
            }
            if (gesucht > a[m]){
                    m = m + 1;
            }
            else {
                    m = m - 1;
            }
            counter++;
        }
        out[0] = -1;
        out[1] = counter;
        return out;
    }
}