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.
Wenn Ihnen javabeginners.de gefällt, freue ich mich über eine Spende an diese gemeinnützigen Organisationen.