Interpolationssuche

Die rekursiv arbeitende Methode search() bekommt vier Parameter übergeben:

• das Array selbst
• der Startindex der Suche
• der Schlussindex der Suche
• die gesuchte Zahl

Die Suche nach dem gefragten Wert gestaltet sich folgendermaßen:
Der Suchbereich wird durch Subtraktion der Werte von Schlusselement und Startelement errechnet. Im zweiten Schritt wird die Differenz der Indizes des Suchraums (Schlussindex - Startindex) gebildet. Als dritte Differenz wird der Startwert vom gesuchten Wert subtrahiert. Mit dieser wird die Indexdifferenz multipliziert und das Ergebnis durch den anfänglich berechneten Suchbereich dividiert. Zum Schluss muss noch der Index des Startelementes addiert werden.

import java.util.Arrays;

public class InterpolationSearch {

    public static void search(int[] intArr, int anfang, int ende, int zahl) {

        int bereich = intArr[ende] - intArr[anfang];
        int grenze = anfang
                + (int) (((double) ende - anfang) * (zahl - intArr[anfang]) / bereich);

        if (intArr.length == 0) {
            System.out.println("Array leer.");
            return;
        }

        if (grenze >= intArr.length) {
            System.out.println(zahl + " nicht im Array enthalten.");
            return;
        }
        System.out.println("Anfang: " + anfang + ", Ende: " + ende
                + ", Grenze: " + grenze);
        if (zahl > intArr[grenze]) {
            search(intArr, grenze + 1, ende, zahl);
        } else if (zahl < intArr[grenze] && anfang != grenze) {
            search(intArr, anfang, grenze - 1, zahl);
        } else if (zahl == intArr[grenze]) {
            System.out.println(zahl + " an Position " + grenze
                    + " des Arrays enthalten.");
        } else {
            System.out.println(zahl + " nicht im Array enthalten.");
        }
    }

    public static void main(String[] args) {
        int[] testArr = { 5, 3, 5, 228, 14, 69, 18, 27, 109, 85 };
        Arrays.sort(testArr);
        search(testArr, 6, testArr.length - 1, 14);
    }
}

Stimmen der errechnete und der gesuchte Wert überein, ist die Suche beendet und das Ergebnis kann ausgegeben werden. Ist der errechnete Wert größer, wird die Suche mit einem Schlussindex wiederholt, der dem berechneten Wert minus eins entspricht und der Anfangsindex bleibt gleich. Es wird also links weitergesucht. Ist er kleiner wird der Anfangsindex auf den um eins erhöhten Grenzwert gesetzt und der Schlussindex bleibt unverändert. Es wird also rechts weitergesucht.