Interpolationssuche

J

Joptionpane

Aktives Mitglied
Abend an alle,

habe mal eben die Interpolationssuche programmiert und dann mal als test eine einfach for-Schleife programmiert um zu sehen was die Suche eigtl. genau bringt. Jedoch kommt bei mir jedes mal das gleiche Ergebnis raus.

hier mal die mit for-Schleife:

Java: 
public static void main(String[] args) {

		double[] a = { 2,4,7,9,12,21,26,31,37};

		System.out.println(IndexSchlüssel(7, a));

	}

	public static int IndexSchlüssel(double z, double[] a) {

			for (int i = 0; i < a.length; i++) {
				if (z == a[i]) {
					return i+1;
				}

			}
		
		return -1;
	}


Wo ist jetzt der Unterschied zwischen dem Code oben und der Interpolationssuche?
 
J

Joptionpane

Aktives Mitglied
Dann sorum: Hier ist mal meine Interpolationssuche:
Java: 
public static int IndexSchlüssel(float z, float[] array) {

		float k = ((z - array[0]) / (array[array.length - 1] - array[0]))
				* (array.length - 1);

		if (z <= k) {
			for (int i = 0; i <= k; i++) {
				if (z == array[i]) {
					return i+1;
				}

			}
		} else if (z > k) {
			for (int i = (int) k; i < array.length; i++) {
				if (z == array[i]) {
					return i+1;
				}

			}
		}

		return -1;
	}

	public static void main(String args[]) {

		float z;
		Scanner sc = new Scanner(System.in);
		System.out.println("Geben Sie den gesuchten Schlüssel ein: ");
		z = sc.nextFloat();

		float[] array = { 1, 3, 5, 7, 10, 11, 12, 13 };

		if (IndexSchlüssel(z, array) == -1) {
			System.out.println("Schlüssel im Array nicht vorhanden!");
		} else {
			System.out.println("Der Schlüssel befindet sich in Fachnummer:"
					+ IndexSchlüssel(z, array));
		}

	}

}

Bei was für einem Beispiel würde diese suche das Richtige ergebnis liefern, jedoch die for-schleife die ich als erstes gepostet habe nicht?
 
M

Marcinek

Gast
Wenn du bei der "Interpolationssuche" (was auch immer das ist) nur ein Element im Array hast, erhälst du eine Divison by Zero Exeption und bei der oberen Suche nicht.
 
M

Michael...

Top Contributor
Joptionpane hat gesagt.:
Bei was für einem Beispiel würde diese suche das Richtige ergebnis liefern, jedoch die for-schleife die ich als erstes gepostet habe nicht?
Zum Vergrößern anklicken....
Die for Schleife ist eine lineare Suche die einfach das Array von vorne durchsucht, bis der Wert gefunden wird.
Allerdings ist der zweite Code nicht viel besser und entspricht auch nicht der Interpolationssuche. Der else Zweig kann gar kein "richtiges" Ergebnis liefern, das i = k gesetzt wird und somit nicht die Anzahl der Suchversuche zurück gegeben wird.

Die Interpolationssuche ist eine rekursive Suche bei der das zu durchsuchende Intervall solange möglichst "günstig" geteilt wird bis der gesuchte Wert gefunden wird. In Deinem zweiten Versuch "teilst" Du das Intervall nur einmalig, wobei Deine Berechnung des "Teilungsindex" nicht korrekt ist.
 
J

Joptionpane

Aktives Mitglied
so, dann erneut, jetzt müssts dann stimmen:

Java: 
public static int IndexSchlüssel(int z, int[] array) {

		int links = array[0];
		int rechts = array.length - 1;

		while (z >= array[links] && z <= array[rechts]) {

			int k = (int) ((((double)z - links) / (array[rechts] - links)) * rechts);
			if (z > array[k]) {
				links = k + 1;
			} else if (z < array[k]) {
				rechts = k - 1;
			} else
				return k+1;
		}
		return -1;
	}

	public static void main(String args[]) {

		int z;
		Scanner sc = new Scanner(System.in);
		System.out.println("Geben Sie den gesuchten Schlüssel ein: ");
		z = sc.nextInt();

		int[] array = { 1, 3, 5, 7, 10, 11, 12, 13 };

		if (IndexSchlüssel(z, array) == -1) {
			System.out.println("Schlüssel im Array nicht vorhanden!");
		} else {
			System.out.println("Der Schlüssel befindet sich an Position: "
					+ IndexSchlüssel(z, array));
		}

	}


Wenn ich es richtig verstanden habe ist der einzigste Unterschied der, dass man hier keine lineare Suche hat und n-mal die Schleife durchlaufen muss oder? Oder gibt es noch einen?

lg
 
C

Camill

Bekanntes Mitglied
Ohne mir das genau angeschaut zu haben, wikipedia liefert eine Beispielimplementierung für die Interpolationssuche.
 
J

Joptionpane

Aktives Mitglied
Ich weiss, das Problem ist ja nicht die Codierung, sondern stelle ich mir nur die Frage wo der Unterschied zwischen dem "Code" (falls man das so nenn kann) in meinem ersten Beitrag und der Interpolationssuche ist, gibt es fälle wo der Code ganz oben ein anderes Ergebnis wie die Interpolationssuche liefert?(ich vermute mal nein). Liegt also der einzige Unterschied an der Laufzeit, das war meine eigtl. Frage.
 
C

Camill

Bekanntes Mitglied
Im Ergebnis Unterscheiden sich die beiden Verfahren nicht, wieso sollten sie das auch - entweder wird das Element gefunden oder nicht. Wie du richtig erkannt hast ist die Interpolationssuche lediglich ein anderes Verfahren das in bestimmten Situationen schneller sein kann als andere Verfahren.
 

Aktuelle Jobs

Neue Themen


Oben