Methoden Binäre Suche als rekursive Variante

M

m-r-t

Mitglied
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:
Java:
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:
Java:
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

Tarrew

Top Contributor
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:

Java:
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:
Java:
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 ;)
 
Zuletzt bearbeitet:
M

m-r-t

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

Java:
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
 
Zuletzt bearbeitet:
Tarrew

Tarrew

Top Contributor
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

m-r-t

Mitglied
jo jetzt funktionierts einwandfrei:)

Java:
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!
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
S Binäre-Suche Algorithmus Java Basics - Anfänger-Themen 1
S Binäre-Suche bei unsortierten Daten Java Basics - Anfänger-Themen 7
L Binäre Suche mit Comparator Java Basics - Anfänger-Themen 5
H Erste Schritte Binäre Suche Java Basics - Anfänger-Themen 37
H Rekursion Binäre Suche Java Basics - Anfänger-Themen 2
L Binäre Suche Java Basics - Anfänger-Themen 2
N Array, lineare Suche, binäre Suche, Programm bleibt unerwartet stehen... Java Basics - Anfänger-Themen 6
B Binäre Suche - Junit Test Java Basics - Anfänger-Themen 6
J Binäre Suche eines Array Java Basics - Anfänger-Themen 5
B Binäre Suche in einem String Array Java Basics - Anfänger-Themen 10
M Binäre Suche Fehler überall =( Java Basics - Anfänger-Themen 2
D Binäre Suche für Integerarray in rekursiver Funktion Java Basics - Anfänger-Themen 5
W Compiler-Fehler Binäre Suche Java Basics - Anfänger-Themen 2
S Multi-Threaded Binäre Suche Java Basics - Anfänger-Themen 29
A Binäre Suche Java Basics - Anfänger-Themen 2
W Binäre Suche Java Basics - Anfänger-Themen 8
O String Binäre Suche Java Basics - Anfänger-Themen 6
M Binäre Suche, Elemente einfügen Java Basics - Anfänger-Themen 2
A Binäre Suche; Java Basics - Anfänger-Themen 6
S binäre semaphore Java Basics - Anfänger-Themen 4
Aprendiendo Gibt es in der JAVA-API eine Funktion, die eine Dezimalzahl in eine binäre Zahl umwandelt? Java Basics - Anfänger-Themen 8
A Binäre Addition Java Basics - Anfänger-Themen 15
V Binäre Suchbäume Java Basics - Anfänger-Themen 1
M Compiler-Fehler Binäre Zahlen in Dezimalzahlen umrechnen Java Basics - Anfänger-Themen 3
K binäre Suchbäume Java Basics - Anfänger-Themen 3
A Binäre Addition Java Basics - Anfänger-Themen 5
E Binäre Bäume Java Basics - Anfänger-Themen 7
0x7F800000 wie pack ich komplette objekte in binäre dateien? Java Basics - Anfänger-Themen 4
F Binäre Exponentiation Java Basics - Anfänger-Themen 9
M binäre Daten als Double einlesen Java Basics - Anfänger-Themen 22
M binäre daten einlesen Java Basics - Anfänger-Themen 2
G Binäre Suchbaum + Erstellung des Programmes Java Basics - Anfänger-Themen 4
R Binäre logische Operatoren Java Basics - Anfänger-Themen 21
F Auf der Suche in π Java Basics - Anfänger-Themen 13
C Suche Nachhilfe in Java Java Basics - Anfänger-Themen 5
T Binärbaum-Suche Implementation Java Basics - Anfänger-Themen 6
A suche dringend Hilfe!! Java Basics - Anfänger-Themen 6
N Operatoren Schreibtischtest der Reihen-Suche nach Aufschluss in die Basics Java Basics - Anfänger-Themen 1
B Suche free SVN Hosting Java Basics - Anfänger-Themen 12
S Java Lineare-Suche Zeitmessung Java Basics - Anfänger-Themen 5
S Java Lineare Suche Java Basics - Anfänger-Themen 1
E Die richtige Suche in der API Java Basics - Anfänger-Themen 1
S suche nach varible POSITION ... fuer das pixel-maennchen Java Basics - Anfänger-Themen 4
E Weg-Suche-Problem rekursiv Java Basics - Anfänger-Themen 12
B Suche Programme mit Fehlern Java Basics - Anfänger-Themen 9
jaleda100 Component für Suche Java Basics - Anfänger-Themen 4
L Suche ein sampel Projekt Java Basics - Anfänger-Themen 2
P Suche Aufwandsgenerator (o-notation) Java Basics - Anfänger-Themen 1
S Suche aktuelles 2D Grafik Tutorial Java Basics - Anfänger-Themen 5
M Suche hilfe bei Array Java Basics - Anfänger-Themen 4
J Methoden Suche effiziente Implementierung für eine Methode Java Basics - Anfänger-Themen 3
D Ich suche nach einer Möglickeit den Webseiten Inhalt per Java zu analysieren Automatisch Java Basics - Anfänger-Themen 3
B String: suche nach Wörter und in List<String> speichern Java Basics - Anfänger-Themen 3
D Erste Schritte Suche Quelltext Java Basics - Anfänger-Themen 7
M Rekursion Minimums Suche Java Basics - Anfänger-Themen 12
J Suche Hilfestellung Java Basics - Anfänger-Themen 10
G Erste Schritte Suche Java Programmierer für kleines Projekt Java Basics - Anfänger-Themen 1
J Suche die Emailadresse Java Basics - Anfänger-Themen 6
H Suche in Text und Markierung Java Basics - Anfänger-Themen 14
H Suche in einem Text Java Basics - Anfänger-Themen 17
J Suche simples Beispiel für die EOFException Java Basics - Anfänger-Themen 1
L Linerae Suche in einem sortierten Array Java Basics - Anfänger-Themen 2
I Innerhalb einer Methode suchen und hinzufügen. Neues Objekt in Suche dann? Java Basics - Anfänger-Themen 8
L Einfache Lineare Suche Java Basics - Anfänger-Themen 7
D Suche nach der Anzahl von Zonen zwischen zwei Punkten Java Basics - Anfänger-Themen 2
M Benutzerdefinierte Suche in einem String - outofbounds Java Basics - Anfänger-Themen 7
X Best Practice SUCHE ein gutes Javabuch! (kein Anfang von 0) Java Basics - Anfänger-Themen 5
A Heap Space Error bei rekursiver Suche in Dateien trotz nur einer Zeile im Speicher Java Basics - Anfänger-Themen 26
M Rekursive Suche in einem Feld Java Basics - Anfänger-Themen 11
S Suche richtigen Typ für Variabel mit den Werten (neu, gebraucht, beschädigt) Java Basics - Anfänger-Themen 7
M Best Practice Programmierstil Graphen-A*-Suche Java Basics - Anfänger-Themen 5
M Suche Hilfe bei sehr kleinen Quelltexten Java Basics - Anfänger-Themen 2
E Suche Klasse die eine Bedinung prüft und einen von zwei Auswahlwerten zurückgibt... Java Basics - Anfänger-Themen 6
D Erste Schritte suche hilfe für db-anbindung Java Basics - Anfänger-Themen 36
S Java Servlet - Suche Java Basics - Anfänger-Themen 1
P Hashing suche Java Basics - Anfänger-Themen 4
K Suche Hilfe bei einfachem Java Code ( Debuggen ) Java Basics - Anfänger-Themen 1
J Variablen Auf der suche nach einem Befehl Java Basics - Anfänger-Themen 2
Farbenfroh Suche Übungsaufgaben: BinaryTree, Stack Java Basics - Anfänger-Themen 0
D Binärbaum Suche Java Basics - Anfänger-Themen 5
U Vererbung Suche Hilfe anhand eines Bsp. Java Basics - Anfänger-Themen 1
L Suche Programmier-Projekt mit Anleitung Java Basics - Anfänger-Themen 3
A Suche Programmierer für Android App Java Basics - Anfänger-Themen 1
H Suche Vergleichstabelle für die Klassen String und StringBuilder Java Basics - Anfänger-Themen 1
X [SUCHE]Mitentwickler Java Basics - Anfänger-Themen 10
P Methoden suche funktion die char wert ausgibt wenn man numerischen wert und radix angibt Java Basics - Anfänger-Themen 1
D Binare Suche Java Basics - Anfänger-Themen 1
C Erste Schritte Bereich angeben bzw Fehler Suche Java Basics - Anfänger-Themen 6
L Suche in dreidimensionalen Arrays Java Basics - Anfänger-Themen 3
P Lineare Suche im Array Java Basics - Anfänger-Themen 5
X verschachtelte suche Java Basics - Anfänger-Themen 8
T Sortieren/Suche klappt nicht ganz (String Array) Java Basics - Anfänger-Themen 2
S Erste Schritte Suche nach einem guten JAVA-Buch (Definition im Thread) Java Basics - Anfänger-Themen 6
G suche den Begriff & wie programmiere ich sowas (ich ändere den Titel dann) Java Basics - Anfänger-Themen 2
M suche/brauche Links über rein GUI Beispielprogramme Java Basics - Anfänger-Themen 4
I Suche Component welches Map ähnelt Java Basics - Anfänger-Themen 11
G Erste Schritte Suche nach Zeichenkette Java Basics - Anfänger-Themen 26
steffomio Suche brauchbares I18N Lib Java Basics - Anfänger-Themen 4
J Suche Tipps zum erstellen von Algorithmen Java Basics - Anfänger-Themen 5
D Artikel-Suche implementieren Java Basics - Anfänger-Themen 7

Ähnliche Java Themen

Anzeige

Neue Themen


Oben