public class Interpolationssuche
{
    int[] zahlen;

    public Interpolationssuche()
    {
        zahlen = new int[20];
        for (int i=0; i<20; i++)
            zahlen[i] = i*2;

        for (int i=1; i<=40; i++)
            testeInterpolationssuche(i);
    }

    public int interpolationssuche(int[] a, int suchzahl)
    {
        // Zunächst ein paar Absicherungen
        if (a == null || a.length == 0)
            return -1;

        if (a.length == 1)
        {
            if (a[0] == suchzahl)
                return 0;
            return -1;
        }

        // Jetzt geht es richtig los...
        // Berechnung der Spannweite
        int minimum = a[0];
        int maximum = a[a.length-1];
        int spannweite = maximum - minimum;

        // Berechnung des wahrscheinlichen Index der Suchzahl
        int intervalle = a.length-1;
        double inkrement = (double) spannweite / intervalle;
        int wIndex = (int) ((suchzahl - minimum) / inkrement);  

        // Wieder eine reine Absicherung
        if (wIndex < 0) wIndex = 0;
        if (wIndex > a.length-1) wIndex = a.length-1;

        // Zahl schon auf Anhieb gefunden?
        if (suchzahl == a[wIndex]) return wIndex;

        // Zahl noch nicht gefunden, also lineares Weitersuchen
        if (suchzahl < a[wIndex])
            return ArrayTools.sucheLinearRueckwaerts(a,wIndex,suchzahl);
        else   
            return ArrayTools.sucheLinearVorwaerts(a,wIndex,suchzahl);
    }


    public void testeInterpolationssuche(int suchzahl)
    {
        int index = interpolationssuche(zahlen,suchzahl);
        System.out.print("Zahl " + suchzahl + " ");

        if (index > -1)
            System.out.println("an Position " + index + " gefunden. Der Wert dort: " + zahlen[index]);
        else
            System.out.println("nicht gefunden.");

    }

    public static void main(String[] args)
    {
        new Interpolationssuche();
    }    

}