Algorithmus für das Binäre Suchverfahren?

... komplette Frage anzeigen

2 Antworten

Binäre Suche:

Hoffe, es ist verständlich genug.

public class BinTest1{

public static void main (String[] args){

int[] feld = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100}; //das Feld, wo eine Zahl gesucht werden soll; wichtig: Muss sortiert sein!

System.out.println("Welche Zahl in Zehnerschritten von 10-100 möchten Sie suchen?");
int ges = InOut.readInt(""); //eingabe der zu suchenden Zahl
//beispielsweise 20
int links = 0; //Variablen zur Eingrenzung des Feldes werden festgelegt
int rechts = feld.length - 1; //aufruf der Methode suche
suche(feld, links, rechts, ges);
}
private static void suche(int[] feld, int links, int rechts, int ges){
while (links <= rechts) { //mit jedem Schleifendurchlauf wird die Anzahl an Zahlen halbiert
int mitte = (links + rechts) / 2; //die Zahl in der Mitte wird herausgesucht
int mitteWert = feld[mitte]; //und in eine Hilfsvariable übergeben

if(mitteWert < ges){ //hilfsvariable wird mit der zu suchenden Zahl verglichen
links = mitte + 1; //wenn ges.ges Wert größer als der mittelwert ist, wird links auf die mitte + 1 gesetzt
} // da die zu suchende Zahl größer ist, muss sie HINTER der mittleren Zahl liegen -> Suchfeld wird eingegrenzt
else if(mitteWert > ges){ //ges.ges Wert ist kleiner: 'rechts' wird auf mitte - 1 gesetzt -> begründung wie oben
rechts = mitte - 1;
}
else{ // stimmt keine der If-Anweisungen, ist der mittlere Wert die gesuchte Zahl
System.out.println("Die Zahl " + ges + " ist an der " + (mitte+1) + ". Stelle zu finden");
break;
}
}
}
}
Antwort bewerten Vielen Dank für Deine Bewertung

Die binäre Suche ist ein rekursiver Algorithmus wo eine sortierte Liste nach einem bestimmten Element durchsucht wird.
Die Idee dahinter ist in etwa folgende: Das Programn schaut sich die Mitte der Liste (hier eine Zahlenfolge aufsteigend sortiert) an.
Wenn es das zu suchende Objekt ist: perfekt
Wenn die Zahl größer ist (wir suchen die 5, sehen aber die 7) dann muss die 5 wohl im linken Teil der Liste sein.
Wenn die Zahl kleiner ist: rechter Teil

Jetzt wird sich der Algorithmus selbst aufrufen um einen neuen Listenbereich zu definieren. -> Die Liste wird halbiert (daher der Name "binär"). Das ganze wird so lange wiederholt bis das Element gefunden wurde oder die Liste nur noch ein Element hat.
Wenn ich am PC bin kann ich dir noch einen Algorithmus in Java posten.

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von Tintenfleck
07.02.2016, 10:03

Cool Danke :)

Wäre sehr nett :)

0

Was möchtest Du wissen?