Interpolationssuche

Die Interpolationssuche ist genau genommen lediglich eine Modifikation der binären Suche, bei der die Unterteilung in Suchabschnitte nicht in der Mitte des Suchbereichs erfolgt, sondern dynamisch gesetzt wird, je nach der Größe des gesuchten Wertes. Ist er hoch, wird er weiter hinten angenommen, ist er niedrig wird er eher weiter vorne vermutet.
Voraussetzung hierzu ist ein sortiertes Array mit wahlfreiem Zugriff.

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

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 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);
        InterpolationSearch is = new InterpolationSearch();
        is.search(testArr, 6, testArr.length - 1, 14);
    }
}

Simmen 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.