Methoden Binäre Suche als rekursive Variante

[m-r-t]

hi leute, das hier wird mein erster Beitrag werden, hoffe das ich es richtig mache und glück habe die richtige hilfe zu finden😉 So, ich sitze vor folgender Übung: Die binäre Suche erhält als Eingabe ein sortiertes Feld als Suchraum sowie das gesuchte Element und liefert als Rückgabewert den Index des gesuchten Elementes im Suchraum. Der Algorithmus arbeitet folgendermaßen:

Als erstes wird das mittlere Element geprüft. Es kann kleiner, größer oder gleich dem gesuchten Element sein. Ist es kleiner als das gesuchte Element, muss das gesuchte in der hinteren Hälfte sein(Falls vorhanden). Wenns größer ist muss es in der vorderen Hälfte suchen und wenns gleich ist, ist die suche beendet. In der zu untersuchenden Hälfte und in den folgenden wird das gleiche verfahren angewendet. Also jedesmal bestimmt das mittlere Element ob und wo weitergesucht wird.

Nun sollen wir die Metode public int search... siehe unten, vervollständigen. Welche den übergebenen String mittels der rekursiven binären Suche im intern gespeicherten Feld sucht und den Index des gesuchten Elementes zurückgibt.

Ganz schön viel reingeschrieben, aber wollte so verständlich wie möglich machen, damit man soweit mein Problem versteht.🙂

Aufgabe:

public class BinarySearcher {

	private String[] feld;
	
	public BinarySearcher(String[] s) {
		this.feld = s;
	}
	
	public int search(String s, int von, int bis) {
		//...
		
	
	public static void main(String[] args) { 
		String[] suchraum = new String[] {"adipiscing", "amet", "consectetur",
				"dolor", "elit", "ipsum", "lorem", "mauris", "sit", "vel"};
		String[] tests = new String[] { "lorem", "vel", "adipiscing", "amat", "a", ""};
		BinarySearcher bs = new BinarySearcher(suchraum);
		for(String t : tests) {
			System.out.println(bs.search(t, 0, suchraum.length - 1));
		}
}
}

Mein Ansatz für die genannte Methode:

public int search(String s, int von, int bis) {
		
		von = 0;
		bis = s.length();
		
		if(von < bis) {
			int mitte = ((von + bis)/2) ;
			String s1 = s.get(mitte);
			if (s1.compareTo(s)<0)
				von = mitte+1;
			else if(s1.compareTo(s)>0)
				bis = mitte;
			else
				return mitte;
		}
		return -1;
	}

Könnt ihr mir sagen ob ich auf dem richtigen weg bin und evtl was noch fehlt oder ich nachschlagen sollte. Vorallem bei Zeile 8(s.get) meckert Eclipse rum. Weil .get bei String nicht geht, aber weiß nicht was ich anders machen soll. Vielen Dank im Voraus🙂

Wenn ich was vergessen haben sollte, hole ich es nach.

 

[Tarrew]

Hey, dein Ansatz ist garnicht mal soo schlecht, hat aber bislang nicht sehr viel mit Rekursion zu tun.

Deine if-Bedingungen sind schonmal garnicht schlecht. Du möchtest ja den String den du suchst, mit dem String an der Position "mitte" im suchraum vergleichen.

Der String an der Position "mitte" im Suchraum ist:
String midString = feld[mitte]; (Das ist praktisch der Ersatz für dein get())
Der String den du suchst ist das s, dass dir als Parameter übergeben wird.

Jetzt gibt es ja 3 Fälle wie du schon gesagt hattest. Die Strings sind gleich, dann kannst du die Position zurückgeben, wie du es ja schon richtig machst. Der String, den du suchst ist kleiner als der String an der Position "mitte" in deinem Suchraum.
Dann liegt der gesuchte String(falls vorhanden) irgendwo zwischen dem "von" und der "mitte".
Das heißt du kannst deine search-Methode nochmal aufrufen, musst allerdings die Grenzen ändern.
Du weißt ja jetzt, dass er im "vorderen" Teil liegt.
Also:

search(s, von, mitte)

Wenn der String den du suchst größer ist, als der String an der Postition "mitte", dann kannste dir ja denken was du ändern musst. 😉

Hier mal eine kleine Vorlage:

public int search(String s, int von, int bis) {
		if (von <= bis) {
			int mitte = (von + bis)/2;
			if (feld[mitte].equals(s)) {
				return mitte;
			}
			if (feld[mitte].compareTo(s) > 0) {
				return ...;
			}
			if (feld[mitte].compareTo(s) < 0) {
				return ...;
			}
		}
		return -1;

		
	}

Sollte dir helfen. Auch würde ich mir nochmal durchlesen, was Rekursion genau ist 😉

 

[m-r-t]

hi tarrew, danke für deine hilfe. Habe mal gleich folgendes ausprobiert:

public int search(String s, int von, int bis) {
    if (von <= bis) {
    int mitte = (von + bis)/2;
    if (feld[mitte].equals(s)) {
    return mitte;
    }
    if (feld[mitte].compareTo(s) > 0) {
    return search(s, von, mitte);
    }
    if (feld[mitte].compareTo(s) < 0) {
    return search(s, bis, mitte);
    }
    }
    return -1;
     
     
    }

Diesmal gibt der was aus, aber klappt noch nicht ganz, falls ich weiterhin auf dem richtigen weg bin:
-1
-1
0
-1
Exception in thread "main" java.lang.StackOverflowError
at BinarySearcher.search(BinarySearcher.java:15) Zeile4
at BinarySearcher.search(BinarySearcher.java:19) Zeile8

 

[m-r-t]

beim letzten if muss es glaube ich so rum, oder?

return search(s, mitte, bis);

 

[Tarrew]

Genau 😉
Theoretisch kannste auch beim 1. return search(s, von, mitte-1) und beim 2. return search (s, mitte+1, bis), weil du die mitte ja schon überprüft hast 😉

 

[m-r-t]

jo jetzt funktionierts einwandfrei🙂

import java.io.*;
import java.util.*;

public class BinarySearcher {

	private String[] feld;
	
	public BinarySearcher(String[] s) {
		this.feld = s;
	}
	
    public int search(String s, int von, int bis) {
    if (von <= bis) {
    int mitte = (von + bis)/2;
    if (feld[mitte].equals(s)) {
    return mitte;
    }
    if (feld[mitte].compareTo(s) > 0) {
    return search(s, von, mitte-1);
    }
    if (feld[mitte].compareTo(s) < 0) {
    return search(s, mitte+1, bis);
    }
    }
    return -1;
     
     
    }
	
	public static void main(String[] args) { 
		String[] suchraum = new String[] {"adipiscing", "amet", "consectetur",
				"dolor", "elit", "ipsum", "lorem", "mauris", "sit", "vel"};
		String[] tests = new String[] {"lorem", "vel", "adipiscing", "amat", "a", ""};
		BinarySearcher bs = new BinarySearcher(suchraum);
		for(String t : tests) {
			System.out.println(bs.search(t, 0, suchraum.length - 1));
		}
}
}

Ausgabe:

6
9
0
-1
-1
-1

Vielen Dank Tarrew🙂 Warst echt eine Hilfe, ging zügig. Deine Hinweise waren für mich sehr einleuchtend😉 Nochmals danke!