public class Indexsuche
{
    int[] zahlen;

    public Indexsuche()
    {
        zahlen = new int[70];
        for (int i=0; i<70; i++)
            zahlen[i] = i*4;
            
        ArrayTools.zeigeArray(zahlen);
            
        for (int sz = 10; sz < 200; sz +=3)
            testeIndexsuche(sz);
    }


    private int[] hilfsArrayErzeugen(int[] hauptArray)
    {
        int[] hilfsArray = new int[11];
        int   max = ArrayTools.getMaximum(hauptArray);
        int   intervall = max / 10;
        int   startwert = intervall;

        hilfsArray[0] = 0;
        int   j = 1;

        for (int i = 1; i < hauptArray.length && j < hilfsArray.length; i++)
        {
            startwert = intervall * j;
            if (hauptArray[i] > startwert)
            {
                hilfsArray[j] = i;
                j++;
            }   
        }   
        
        return hilfsArray;
    }
    
    public int indexsuche(int[] a, int suchzahl)
    {
        // Ein paar Vorsichtsmassnahmen
        if (a == null || a.length == 0)
            return -1;

        if (suchzahl < a[0] || suchzahl > a[a.length - 1])
            return -1;      
            
        // Erzeugung des Index-Arrays
         int[] indexArray = hilfsArrayErzeugen(a);
        
        // Suchen der Startposition im Index-Array 
        int i=1;
        while (suchzahl > a[indexArray[i]]) i++;
        int start = indexArray[i-1];
        
        // Suche im uebergebenen Haupt-Array
        int index = ArrayTools.sucheLinearVorwaerts(a, start, suchzahl);
        return index;
    }
    
    
     public void testeIndexsuche(int suchzahl)
    {
        int index = indexsuche(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 Indexsuche();
    }    

}