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:
- 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 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.
Algorithmen
