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. 😳
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:
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
 
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:
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...
 
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;
  }
}
 
Black-Dragon hat gesagt.:
[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.
Zum Vergrößern anklicken....
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.
 
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 ?
	
		
	
		   	
		
	}		

}
 
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:
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
 

Aktuelle Jobs

Neue Themen

Ähnliche Themen

Array, lineare Suche, binäre Suche, Programm bleibt unerwartet stehen...
Antworten: 6
Lineare Suche / Binäre Suche
Antworten: 2
String Binäre Suche
Antworten: 6
Binäre Suche im Array mit StackOverflowError
Antworten: 3
Binäre Suche eines Array
Antworten: 5

Zurück
Oben