binaeres such problem.

[Demoncwue]

hallo an alle...
versuche seit längerem eine rekursive binaere suche zu realisieren...

allerdings ist in meinen code ein fehler. die while schleife wird leider nicht beendet. allerdings weiß ich nicht warum
ein weiteres problem ist die methode startsWith.. wenn ich einen textstring als schlüssel eintrage dann kommt es zu einem stackoverflow. es funktioniert nur wenn ich nach einem einzelnen buchstaben suche.

kann mir ijmd vlt helfen? das wäre prima...

anbei mein code:

/*
 * @author  
 * Version 2 26.11.08 um 16.45uhr
 */

public class bineareSuchetest {

	public static int binSucheHilf(String[] liste,String schluessel,int oben,int unten){
	int zahl;	
	int mitte = (oben-unten)/2;
		while(unten < oben){
			if(liste[mitte].startsWith(schluessel) == true){
				System.out.println("Der Sucheintrag wurde an Stelle " + mitte + " gefunden.");
				return mitte;
				}
			else{zahl = liste[mitte].compareTo(schluessel);}
			
				if(zahl<0){binSucheHilf(liste,schluessel,mitte-1,unten);}
				else{binSucheHilf(liste,schluessel,oben,mitte+1);}		
			//	break;
				}
			
		return -1;
	}
	
    public static int binSuche(String[] liste, String schluessel){
    	
    	
    	int mitte = binSucheHilf(liste,schluessel,liste.length,0);
    	int key = mitte;
    	System.out.println("Der gesuchte eintrag ist an stelle" + key);
		return key;
      
    	}

    public static void main(String[] args){
 
         String[] cdRegal = {"ACDC - Back in Black",
                "ACDC - Black Ice",
                "Air - Pocket Symphony",
                "Beastie Boys - Hello Nasty",
                "Lenny Kravitz - Let Love Rule",
                "Massive Attack - Mezzanine",
                "Oasis - Heathen Chemistry",
                "ZZ-Top - Afterburner" };
         String suchenach = "A";
         System.out.println(binSuche(cdRegal,suchenach));

	}
    }

 

[Michael182828]

Hallo,
deine while schleife sagt doch aus
gehe aus der schleife raus wenn unten kleiner ist als oben.

aber du zählst weder unten hoch oder oben runter
Wie willst du den aus der schleife kommen ???

  public static int binSucheHilf(String[] liste,String schluessel,int oben,int unten){ 
   int zahl;    
   int mitte = (oben-unten)/2; 
      while(unten < oben){ 
         if(liste[mitte].startsWith(schluessel) == true){ 
            System.out.println("Der Sucheintrag wurde an Stelle " + mitte + " gefunden."); 
            return mitte; 
            } 
         else{zahl = liste[mitte].compareTo(schluessel);} 
          
            if(zahl<0){binSucheHilf(liste,schluessel,mitte-1,unten);} 
            else{binSucheHilf(liste,schluessel,oben,mitte+1);}       
         //   break; 
         HIER SOLLTE SPÄTESTENS EIN WERT VERÄNDERT WERDEN 
                 oben++ oder oben--;
            oder 
                unten++ oder unten--;
            } 
          
      return -1; 
   }

Gruß Michael

 

[Demoncwue]

Würde ich dann nicht die Grenzen der binären suche verfälschen?
wenn ich einfach zum beispiel den wert oben-- mache...

 

[Gast]

ich habe das mal mit oben++ ausprobbiert und hatte einen fehler. wäre nett wenn jemand helfen könnte^^

 

[Leroy42]

Einfach die while-Schleife (unten <= oben) in eine
If-Abfrage ändern und die rekursiven Aufrufe returnen.

 

[Gast]

public static int binSucheHilf(String[] liste,String schluessel,int oben,int unten){
int zahl;
int mitte = (oben-unten)/2;
if(unten < oben){
if(liste[mitte].startsWith(schluessel) == true){
System.out.println("Der Sucheintrag wurde an Stelle " + mitte + " gefunden.");
return mitte;
}
else{zahl = liste[mitte].compareTo(schluessel);}

if(zahl<0){binSucheHilf(liste,schluessel,mitte-1,unten);}
else{binSucheHilf(liste,schluessel,oben,mitte+1);}
oben++;
unten++;
}

return -1;
}

public static int binSuche(String[] liste, String schluessel){


int mitte = binSucheHilf(liste,schluessel,liste.length,0);
int key = mitte;
System.out.println("Der gesuchte eintrag ist an stelle" + key);
return key;

}



}


damit bekomme ich als antwort immer ist an der stelle -1. wie ist das zu erklären?

 

[Gast]

hi, wenn man diesen code rekursiv schreiben wolle, müsse man ja die schleife durch ei if ersetzen. aber was meint ihr mit rekursiven aufrufe returnen?

 

[Dominici]

hat denn jetzt jemand eine lösung rausbekommen die funktioniert?