Binäre Suche in einem String Array

B

Black-Dragon

Mitglied
Hallo zusammen,

ich bin neu hier, fange gerade erst mit dem Programmieren an, und bin wohl schon ein wenig älter als die meisten Anfänger. :oops:
Ich habe hier im Forum zwar schon einiges gelesen, die Suche genutzt und auch gegooglet, aber leider nicht das richtige gefunden.
Ich hoffe hier kann mich mal jemand aufklären, ich verstehe nicht was an meinem code falsch ist.

Das Programm soll folgendes können...
- bestimmung einer String Array-Länge durch user Eingabe, wobei diese mindestens 6 betragen muss
- Erzeugung eines Arrays, einlesen der Strings durch user Eingabe.
- Dann soll der user noch einen der Strings eingeben können, und das Programm soll dann die Position des Strings anzeigen.

folgendes habe ich geschrieben:

Java:
  import java.util.Arrays;
import java.io.*;

public class Aufgabe_4 {

	public static void main(String[] args) throws IOException 
	{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		
		int laenge;								// Array-Laenge
		String [] userArray;
		String wortSuche;
		
		
		
		do 
		{
			System.out.print("Wie lang soll das Array sein: ");			// Abfrage wie lang das Array sein soll.
			laenge = Integer.parseInt(in.readLine());					// Einlesen der Laenge
			
			if(laenge <6)												// Falls kleiner als 6, Hinweis auf Mindestlaenge
			{
				System.out.println();
				System.out.println("Bitte mindestens eine laenge von 6 wählen! ");
				System.out.println();
			}
				
		} while (laenge < 6);							//Abfrage solange Mindestlaenge nicht eingeben wird.
		
		userArray = new String [laenge];				
		System.out.println();
		System.out.println("Bitte geben Sie nacheinander "+laenge+" Strings ein und bestätigen sie jweils mit Enter. ");
		System.out.println();
		
		for (int i=0; i <= userArray.length-1; i++) 			// Einlesen der gewählten Anzahl an Strings.
		{
			userArray[i] = in.readLine();
		}
		
		for (int i=0; i <= userArray.length-1; i++) 			// Konvertierung der Strings in Kleinbuchstaben
		{
			userArray[i] = userArray[i].toLowerCase();
 		}
		
		Arrays.sort(userArray);							// Alphabetische Sortierung der Worte
		
		System.out.println();
		System.out.print("Bitte Wort zur Suche eingeben: ");
		wortSuche = in.readLine();
		wortSuche = wortSuche.toLowerCase();
		System.out.println();
		
		int grenzeLinks = 0, grenzeRechts = userArray.length-1;
		int mitte = (grenzeLinks + grenzeRechts)/2;
		boolean gefunden = false;
		
		
		
		
		while (gefunden == false) 
		{
				
				if (wortSuche.equals(userArray[mitte])) 								
				{
					gefunden = true;
					System.out.println("Position: "+ Arrays.asList(userArray).indexOf(wortSuche));
				}
				else 
					if (wortSuche.compareTo(userArray[grenzeLinks]) < 0            ||wortSuche.compareTo(userArray[grenzeRechts]) > 0) 
					{
						System.out.println("Das gesuchte Wort existiert nicht."); 
					}
				
				if (wortSuche.compareTo(userArray[mitte]) > 0) 
				{
					grenzeLinks = mitte+1; 
				}
				else 
					if (wortSuche.compareTo(userArray[mitte]) < 0)
					{
						grenzeRechts = mitte-1;
					}
		 } 
		   
		
			
	}

}


Das Programm liest auch alles ein, und falls ich einen String suche, der nicht im Array ist, bekomme ich auch eine Meldung, dass der Strings nicht existiert, wenn ich allerdings einen String suche, der auch im Array ist, passiert gar nichts.
Ich hoffe hier kann mir jemand erklären was ich falsch mache.

Edit: Achso es soll mit der "Binären suche" funktionieren.
 
Zuletzt bearbeitet:
Thallius

Thallius

Top Contributor
Du setzt zwar eine neue Grenze wenn der String NICHT in Mitte drin ist aber deine Mitte bleibt immer gleich. Somit testest du auch immer die gleichen zwei Strings uaf Gleichheit.

Gruß

Claus
 
B

Black-Dragon

Mitglied
Oh daran hab ich ja überhaupt nicht gedacht! Danke Claus, es funktioniert jetzt alles bestens ! :D
 
B

Black-Dragon

Mitglied
Eine Frage hätte ich aber doch noch... Wie bewerkstellige ich es denn, dass der user beliebig oft ein Wort suchen kann, also bis er ein Ende wünscht. Mit einer do-while Schleife, wie ich es bei Integer Zahlen z.B. machen würde, funktioniert das ganze nicht ohne weiteres, da Strings ja nicht editierbar sind. Ich dachte dann an die Verwendung von StringBuffer oder StringBuilder, allerdings hab ich da keinen Schimmer wie ich das Suchwort mit dem Array Inhalt vergleichen soll, die Methode .comapreTo() funktioniert ja leider nicht. Ich habe im Netz leider nichts passendes gefunden.
 
Zuletzt bearbeitet:
A

arilou

Bekanntes Mitglied
Probier' die do-while-Schleife doch aus, soweit ich das sehe, kann das durchaus funktionieren.
 
B

Black-Dragon

Mitglied
Hab ich natürlich schon, und es funktioniert nicht. Wie bereits erwähnt liegt das wohl daran, dass die Variable ja nur eine Referenz auf den String ist, und ein String nunmal nicht einfach editierbar ist. Ich hab aber leider keiner Ahnung wie ich es angehen soll. Hab schon einiges probiert, kriege es aber einfach nicht hin. Kann sonst auch leider niemanden fragen...
 
Flown

Flown

Administrator
Mitarbeiter
Ich habe dir mal eines meiner Übungen als Analogie umgebastelt wie man sowas macht:

Java:
import java.util.Scanner;

public class BinaryIntSearch {
  public static void main(String... args) {
    try (Scanner input = new Scanner(System.in)) {
      System.out.print("Bitte Länge des Arrays eingeben: ");
      int length = input.nextInt();
      int[] userInput = new int[length];
      for (int i = 0; i < length; i++) {
        System.out.print("Eingabe [" + i + "]: ");
        userInput[i] = input.nextInt();
      }
      do {
        System.out.print("Die zu suchende Zahl: ");
        int criteria = input.nextInt();
        int pos = binarySearch(userInput, criteria);
        if (pos == -1) {
          System.out.println("Zahl ist im Array nicht vorhanden.");
        } else {
          System.out.println("Zahl ist an der " + pos + ". Stelle.");
        }
        System.out.println("Suche wiederholen(y/n)?");
        // clear "\n" from input
        input.nextLine();
      } while (input.nextLine().equalsIgnoreCase("y"));
    }
  }
  
  public static int binarySearch(int[] array, int criteria) {
    int low = 0;
    int high = array.length - 1;
    
    while (low <= high) {
      int mid = low + high >>> 1;
      if (array[mid] < criteria) {
        low = mid + 1;
      } else if (array[mid] > criteria) {
        high = mid - 1;
      } else {
        return mid;
      }
    }
    return -1;
  }
}
 
A

arilou

Bekanntes Mitglied
[do-while-schleife] Hab ich natürlich schon, und es funktioniert nicht. Wie bereits erwähnt liegt das wohl daran, dass die Variable ja nur eine Referenz auf den String ist, und ein String nunmal nicht einfach editierbar ist.
Keine Ahnung, was du da versuchst, aber der vermutete Grund dürfte schlichtweg nicht zutreffend sein. Aber ohne dass du deinen Versuch mal präsentierst, können wir auch nicht den Fehler darin finden...
So ähnlich, wie Flown es macht, geht das auch mit Strings.
 
B

Black-Dragon

Mitglied
Also... Ich habe jetzt schonmal hinbekommen, dass man noch ein Wort suchen kann... Allerdings wird bei mir dann folgendes ausgegeben, wenn ich "j" eingebe:

"Bitte Wort zur Suche eingeben:
Das gesuchte Wort existiert nicht.

Bitte Wort zur Suche eingeben: "

Dann funktionierts allerdings. Wie bekomme ich die unerwünschte Meldung weg ? Bedingungen ändern, schon klar, ich weiß nur nicht wie. :)


Java:
import java.util.Arrays;
import java.io.*;

public class Aufgabe_4 {

	public static void main(String[] args) throws IOException 
	{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		
		int laenge;								// Array-Laenge
		String [] userArray;
		String wortSuche;
		
		
		
		
		do 
		{
			System.out.print("Wie lang soll das Array sein: ");			// Abfrage wie lang das Array sein soll.
			laenge = Integer.parseInt(in.readLine());					// Einlesen der Laenge
			
			if(laenge <6)												// Falls kleiner als 6, Hinweis auf Mindestlaenge
			{
				System.out.println();
				System.out.println("Bitte mindestens eine laenge von 6 wählen! ");
				System.out.println();
			}
				
		} while (laenge < 6);							//Abfrage solange Mindestlaenge nicht eingeben wird.
		
		userArray = new String [laenge];				
		System.out.println();
		System.out.println("Bitte geben Sie nacheinander "+laenge+" Strings ein und bestätigen sie jweils mit Enter. ");
		System.out.println();
		
		for (int i=0; i <= userArray.length-1; i++) 			// Einlesen der gewählten Anzahl an Strings.
		{
			userArray[i] = in.readLine();
		}
		
		for (int i=0; i <= userArray.length-1; i++) 			// Konvertierung der Strings in Kleinbuchstaben
		{
			userArray[i] = userArray[i].toLowerCase();
 		}
		
		Arrays.sort(userArray);							// Alphabetische Sortierung der Worte
		
										
	char nochmal = 'n';									// Variable zur Abfrage ob noch eine Suche erwünscht. 
	
		
	do
	{
	
		System.out.println();
		System.out.print("Bitte Wort zur Suche eingeben: ");	
		wortSuche = in.readLine();
		wortSuche = wortSuche.toLowerCase(); 
		
		
		
	
		
		System.out.println();
		
		
		
		int li = 0, ri = userArray.length-1;		// festlegung der linken und rechten Grenze
		int mi = (li+ri)/2;						 	//  Berechnung der Mitte des Arrays
		boolean gefunden = false; 
		
		
		
		
		while (gefunden == false) 
		{
				if (wortSuche.equals(userArray[mi])) 		// Prüfung ob der gesuchte String in der Mitte liegt						
				{
					System.out.println("Position: "+ Arrays.asList(userArray).indexOf(wortSuche)); // Ausgabe der Position
					System.out.print("Soll noch ein Wort gesucht werden ? Ja (j) Nein (n): ");				
					nochmal = (char) System.in.read();
					gefunden = true; 	// beendet die Schleife	
					
				}
				else
					if (wortSuche.compareTo(userArray[li]) < 0 || wortSuche.compareTo(userArray[ri]) > 0) 
					{
						System.out.println("Das gesuchte Wort existiert nicht."); 
						gefunden = false;
						break;			
					}
				
		
							
				if (wortSuche.compareTo(userArray[mi]) > 0) 	// Falls das gesuchte Wort größer ist, entsprechende verschiebung
				{												// der linken grenze und Neuberechnung der Mitte
					li = mi+1; 
					mi = (li + ri)/2;
				}
				else 
					if (wortSuche.compareTo(userArray[mi]) < 0) // Falls das gesuchte Wort größer ist, entsprechende verschiebung
					{												 // der rechten Grenze und Neuberechnung der Mitte. 
						ri = mi-1;
						mi = (li + ri)/2;
					}
				
			
		 } 	// Ende der while Schleife
			
	} while (nochmal == 'j'); // warum wird immer " Das gesuchte Wort existiert nicht ausgegeben wenn ich wiederholen will ?
	
		
	
		   	
		
	}		

}
 
A

arilou

Bekanntes Mitglied
Weil bei

nochmal = System.in.read() ;

nur 1 Zeichen aus dem Input-Datenstrom entnommen wird (das 'j' oder 'n'), aber System.in auf eine Eingabe mit abschließendem <ENTER> wartet. Und dieses Zeilenende ((char) 13 , (char) 10) ist noch im Eingabestrom und wird dann gleich als "leere Eingabe" in

wortSuche = in.readLine();

eingelesen...

PS: Man darf bei dir nur dann entscheiden, ob man nochmal suchen will, wenn der Begriff gefunden wurde?
Eigentlich gehört diese Abfrage nicht in den "gefunden"-Zweig der Suchschleife, sondern ja wohl nach der Schleife, oder?
 
Zuletzt bearbeitet:
B

Black-Dragon

Mitglied
Danke, das habe ich noch nicht gewusst. Jetzt funktioniert alles bestens!

Die Abfrage stand auch ursprüglich außerhalb der Schleife, dass sie im "gefunden" Zweig gelandet ist, liegt daran, dass ich sämtliche Konstellationen ausprobiert habe, als es nicht laufen wollte. Konnte mir ja den Fehler nicht erklären^^
Jetzt weiß ich es besser. ;)

mfg
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
RudiRüssel Binäre Suche, unsortiert, lokales Maximum Java Basics - Anfänger-Themen 15
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
M Methoden Binäre Suche als rekursive Variante Java Basics - Anfänger-Themen 5
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
Y Suche von Studenten anhand Ihrer Eigenschaften. Java Basics - Anfänger-Themen 1
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

Ähnliche Java Themen

Anzeige

Neue Themen


Oben