Erste Schritte Binäre Suche

H

HO!

Mitglied
Moin!

Als Java-Einsteiger habe ich mich in meinem Unikurs gerade damit auseinandergesetzt, die Programmiersprache zu lernen. Da ich aktuell nicht weiterkomme, bin ich auf dieses Forum gestoßen und werde hier sicherlich in der nächsten Zeit noch etwas rumstöbern und mir Anregungen holen.

Zunächst einmal habe ich (wie wohl jeder Einsteiger) mich an der binären Suche versucht, die mein Übungsbuch vorschlägt. Diese soll innerhalb eines Arrays von 0-9 die gesuchte Zahl finden (Konsole).

Das klappt auch soweit ganz gut, solange es sich um Zahlen zwischen 1 und 8 handelt, die 0 und die 9 wird nicht gefunden und ich frage mich, warum das der Fall ist. Könnt ihr mir da weiterhelfen?

Java: 
package binaereSuche;
@SuppressWarnings( "javadoc" )
public class BinaereSuche {
       public static void main( String[] args ) {
                    
             int[] array = new int[10];
             for ( int i = 0; i < 10; i++ ) {
                    array[i] = i;
             }
             for ( int i : array ) {
                    System.out.println( i );
             }
             
             int gesucht = 9; // gesuchte Zahl
             int anzahl = 10; // Anzahl der Zahlen
             int mitte = 0;
             int unten = 0;
             int oben = array.length - 1;
             int durchlaeufe = 0;
             boolean gefunden = false;
             System.out.println( "Anzahl = " + anzahl );
             System.out.println( "Gesucht = " + gesucht );
             System.out.println( "Mitte = " + mitte );
             System.out.println( "Oben = " + oben);
             System.out.println( " unten = " + unten);
             while ( gefunden != true && ( oben - unten ) > 1 ) { // Abbruchbedingung
                  
                 mitte = ( int ) ( ( oben - unten ) / 2 + unten );
                    System.out.println( "Aktuelles Element = " + array[mitte] );
                    durchlaeufe++;
                  
                    if ( array[mitte] == gesucht ) {
                           gefunden = true;
                           System.out.println( "Gesuchtes Element " + gesucht + " ist Element " + mitte );
                           System.out.println( "Benötigte Durchläufe: " + durchlaeufe );
                           break;
                    }
                    if ( array[mitte] < gesucht ) {
                           unten = mitte;
                           System.out.println( "IF-Zweig - neues Mitte: " + mitte );
                    }
                  
                    else {
                           oben = mitte;
                           System.out.println( "ELSE-Zweig - neues Mitte: " + mitte );
                    }
                  
             }
             
             if ( !( ( oben - unten ) > 1 ) ) System.out.println( "Gesuchtes Element nicht gefunden!" );
       }
}
 
Ein Problem sind die Abbruchbedingung der Schleife und die Gefunden-Bedingung am Ende, denn wenn unten=8 und oben=9 ist, ist die Differenz 1 und somit die Bedingung erfüllt, obwohl die 9 noch nicht geprüft wurde.

Ein zweites Problem ist die Berechnung der neuen Unter- bzw. Obergrenze. Angenommen es ist wieder unten=8 und oben=9. Dann ergibt sich mitte=8, denn ganzzahlig ist 1/2+8=8. Es würde also erneut unten=8 und oben=9 gesetzt, so dass 9 nie überprüft wird.
 
Hallo Meniskusschaden,

vielen Dank, das hat mir schon mal sehr weitergeholfen! Ich habe nach einigem Rumprobieren auch die richtige Lösung rausgefunden.

Nun möchte ich ein Unterprogramm auf dieses Programm Binäre Suche zugreifen lassen, d.h. in einer anderen Klasse soll die gesuchte Zahl eingegeben werden und hier soll dann auch ausgegeben werden, ob die gesuchte Zahl im Array ist. Die binäre Suche bildet daher die zweite Klasse.

Ich benötige ein paar Anregungen, wie sich das bewerkstelligen lässt, könnt ihr mir ein paar Stichworte geben? Ich hatte eben überlegt, dass sich das mit Gettern und Settern lösen lässt, d.h. als Setter die gesuchte Zahl in der ersten Klasse eingeben, die dann als Getter in der Klasse "Binäre Suche" übertragen wird? Ist das ein richtiger Gedanke oder was empfiehlt ihr?
 
Du könntest dir ein Objekt erstellen das BinarySearch heißt und diese Objekt behandelt dann den Suchvorgang. Die Suche wird dabei durch eine Methode angestoßen. Die Modellierung würde sich dann so gestallten das du der BinarySearch ein Array und die gesuchte Zahl übergibst
Java: 
public class BinarySearch {
    public int search(int[] array, int number) {
        // Suchalgorithmus hier rein
    }
}
In einer anderen Klasse würdest du dein Programm starten und ein BinarySerach Objekt erstellen und darauf die search(...,...) Methode aufrufen.
Java: 
public class BinarySerachExample {
    public static void main(String[] args){
        int[] array = new int[] { 0 , 1, 2, 3, 4, 5, 6, 7, 8, 9};
        BinarySearch binarySearch = new BinarySearch();
        int number = binarySearch.search(array, 5);
        System.out.println(number)
    }
}

Beste Grüße,
Jar
 
Danke, das hilft mir ja schon mal gut weiter! 🙂

Ich hatte ja bisher das Array sowie den Suchalgorithmus in einer gemeinsamen Klasse definiert. Nun will ich ein übergebenes Array ( + gesuchter Zahl) mithilfe des Binären Suchalgorithmus in einer anderen Klasse suchen.
Eignet sich dafür mein obiger Suchalgorithmus überhaupt? Ich überlege seit einiger Zeit, wie ich diese Zeilen hier
Java: 
  int[] array = new int[10];
             for ( int i = 0; i < 10; i++ ) {
                    array[i] = i;
             }
             for ( int i : array ) {
                    System.out.println( i );
             }
            
             int gesucht = 9; // gesuchte Zahl
             int anzahl = 10; // Anzahl der Zahlen
             int mitte = 0;
             int unten = 0;
             int oben = array.length - 1;
             int durchlaeufe = 0;
             boolean gefunden = false;
, die ja das Array erstellen und die Variablen definieren, nun auslagere. Beispielsweise habe ich durch "int anzahl = 10;" die Anzahl der Elemente im Array schon festgelegt, aber die weiß ich ja künftig nicht, da ich ja prinzipiell jedes Array nehmen kann.

Hat jemand eine Idee?
 
Ah, dankeschön! 🙂 Das klappt soweit ganz gut. Das Array muss allerdings bei mir Integers enthalten, damit gesucht wird (da die Suchmethode ja auch ints anfordert). Gibt es auch die Möglichkeit, dass man mithilfe der binären Suche (wie oben) auch Arrays mit Strings, Bytes, Chars usw. übergeben kann? Wie wäre da der Lösungsansatz?
Ideal wäre eine universelle Lösung, d.h. dass man jedes Array (egal, was es enthält) übergeben kann
 
Stichwort ist Generics, aber das geht soweit ich weiß nicht mit nativen Datentypen. Dafür musst du dann eine Liste benutzten. Beispielsweise List<Integer>, List<String> ... List<DeinObjekt>
 
Also man könnte natürlich für alle Datentypen (zB byte, long, int, char, String...) eine neue Methode erstellen und dann entsprechend den Algorithmus immer kopieren, das macht den Code aber sehr lang.
Also
Java: 
public char search(char[] array, char c)
oder
Java: 
public int search(int[] array, int i)
Ginge das nicht als Schleife? Dass jedes übergebenes Array durchsucht werden kann?
 
HO! hat gesagt.:
immer kopieren
Zum Vergrößern anklicken....
Regel Nr 1. Don't repeat yourself.
Klar könnte man alles doppelt und dreifach in verschachtelten If Zweigen unterbringen. Das ist aber extrem schlechter Stil. Witzigerweise wird es in "Arrays" so gemacht.

Java: 
public class BinarySearchExample {
    public static void main(String[] args) {
        BinarySearch<Integer> integerBinarySearch = new BinarySearch<>();
        Integer[] array = new Integer[] { 0 , 1, 2, 3, 4, 5, 6, 7, 8, 9};
        integerBinarySearch.search(array, 5);
    }
}
Java: 
public class BinarySearch<T> {
    /**
    * Verwendet die binäre Suche um ein Element in einem generischen Array zu finden.
    * @param array - Array in dem gesucht wird.
    * @param element - Element nach dem gesucht wird.
    * @return Gibt den Index des Elements zurück.
    */
    public int search(T[] array, T element) {
        return Arrays.binarySearch(array, element);
    }
}
Ich hatte leider keine Zeit Binary Search eben fix zu schreiben, deswegen benutzte ich hier den schon vorhandenen Algorithmus.

Man könnte an dieser Stelle auch einfach ein Object[]-Array benutzten... dann kann man sich aber auch die ganze Klasse schenken und einfach Arrrays.binarySearch(); benutzen 😛
 
Ok, die vorgegebene Klasse von Java Arrays.binarySearch kann man benutzen, bei mir sieht die Aufgabenstellung leider vor, das ohne diese eigene Javaklasse zu machen, d.h. mit dem o.g. Suchalgorithmus.

Wenn ich Deinen Code richtig verstehe, wird wieder ein int-Array übergeben, d.h. es gibt keine Möglichkeit, den o.g. Suchalgorithmus "universal" zu gestalten, dass ein beliebiges Typen-Array übergeben werden kann? Oder sehe ich was falsch?
 
Auf die Art wie dein Algorithmus geschrieben ist wohl nicht.
Code: 
"array[mitte]< gesucht"
Wenn du ein String Array hast, in dem Hund Katze und Maus steht. Wie willst du entscheiden, was größer oder kleiner ist. Du müsstest hier mit comparable arbeiten und eine Vergleichsmöglichkeit schaffen.
Hast du für das Problem eine spezielle Aufgabenstellung? Wenn ja, her damit 😛

Java: 
    // Like public version, but without range checks.
    private static int binarySearch0(Object[] a, int fromIndex, int toIndex,
                                     Object key) {
        int low = fromIndex;
        int high = toIndex - 1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            @SuppressWarnings("rawtypes")
            Comparable midVal = (Comparable)a[mid];
            @SuppressWarnings("unchecked")
            int cmp = midVal.compareTo(key);

            if (cmp < 0)
                low = mid + 1;
            else if (cmp > 0)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found.
    }

Das ist die Variante die hinter Arrays.binarySearch() steckt. Und hier wird Comparable verwendet.

Der Aufruf wird auch mithilfe von Generics gemacht.
Java: 
public static <T> int binarySearch(T[] a, T key, Comparator<? super T> c) {
        return binarySearch0(a, 0, a.length, key, c);
    }

Das würde also gehen. Du müsstest allerdings deine Algorithmus umschreiben.
 
Hmm, "Generics" kenne ich noch nicht. Aber ich habe das noch nicht ganz verstanden:
Wenn ich nun statt eines int-Arrays ein char-Array übergebe (und die entsprechenden int-Variablen in char-variablen umschreibe im Quellcode), dann funktioniert es auch problemlos, d.h. er zeigt mir an, ob mein gesuchtes Element im char-Array enthalten ist.

Insofern dachte ich, dass es dann auch mit byte-Arrays, long-Arrays usw. funktionieren würde.

Es soll halt ohne die Arrays.binarySearch() gelöst werden, dass ein beliebiges Array mit einem gesuchten Element übergeben wird und mithilfe der Binären Suche durchsucht wird. Ich habe ja nun eine Methode, um ein Array nach Integern zu durchsuchen und kann dieselbe Methode umschreiben, um es nach char-Elementen (long, byte...) zu durchsuchen, aber ich würde gerne einmal alle Methoden in den Quelltext schreiben, sodass danach jedes beliebige Array übergeben werden kann.
Dazu könnte ich jetzt für jede Methode den kompletten Code erneut reinkopieren, aber das ist ja, wie oben schon geschrieben wurde, nicht angebracht. Gibt es daher eine elegantere Lösung?
 
Ja, die schon erwähnte. So ähnlich müsstest du das auch bauen.
Ein char ist übrigens auch nichts anderes als eine Zahl für Java. Mit einem String sieht das aber schon wieder anders aus, oder mit einem speziellen Objekt z.b: Auto, oder Baum^^
 
Ok, d.h. ich müsste also wie Du in #13 geschrieben hast, meinen Algorithmus umschreiben und kann ihn in der Form, wie er bisher existierte, nicht benutzen für mehrere Arrays (String-Arrays mal außen vor, von mir aus erst mal nur primitive Datentypen)?
 
Ja das würde ich sagen, du müsstest deinen Code verändern.
Eine einfache Idee wäre ein Array aus dem WrapperTyp Number zu erstellen und dann wie folgt deinen Algorithmus aufzubauen:
Java: 
public class BinarySearch {
    public int search(Number[] data, Number key) {
        int low = 0;
        int high = data.length;

        while (high >= low) {
            int middle = (low + high) / 2;
            if (data[middle].equals(key)) {
                return middle;
            }
            if (data[middle].doubleValue() < key.doubleValue()) {
                low = middle + 1;
            }
            if (data[middle].doubleValue() > key.doubleValue()) {
                high = middle - 1;
            }
        }
        return -1;
    }
}
Java: 
public class BinarySearchExample {   
    public static void main(String[] args) {
        BinarySearch binarySearch = new BinarySearch();
       
        Number[] data = new Number[] { 0x1, 0x2, 0x3, 0x4, 42, 55.05};
       
        int index = binarySearch.search(data, 55.05);

        if(index == -1) {
            System.out.println("Gesuchtes Element nicht gefunden!");
        } else {
            System.out.println("Das Element befinded sich am Index: " + index);
        }
    }
}

Ausgabe:
Code: 
Das Element befinded sich am Index: 5
 
Super, vielen Dank! das klappt insoweit auch ganz gut.

Als "erweiterte Aufgabe" habe ich mir überlegt, wie es wäre, wenn ich kein "universelles Array" hätte, sondern nur ein String-Array. Das Thema hatten wir ja schon in #13 angeschnitten, hier wurde mit Comparable gearbeitet, allerdings auch – auch vor dem Hintergrund eines "universellen Arrays", was übergeben wird – mein ursprünglicher Programmcode geändert.

Frage: Wie würde man die Sache lösen, indem man so wenig von dem ursprünglichen Programmcode ändert wie möglich? Gäbe es eine Option mit der CompareTo()-Methode?
 
Also ich habe nun noch etwas rumgespielt und bin zu dem Ergebnis gekommen, dass es tatsächlich am einfachsten ist, mit Comparable (compareTo()) zu arbeiten. Mein Problem ist allerdings nunmehr, dass ich Schwierigkeiten dabei habe zu überprüfen, ob sich ein String in einem String-Array befindet. Hat hier jemand einen Tipp?
 
Du musst dein komplettes Array durchgehen und darin den gesuchten String mit dem aktuellen vergleichen.
In etwa so könnte das aussehen 🙂
Java: 
private boolean isStringInArray(String[] array, String gesuchterString) {
    for(String s : array) {
        if(s.equals(gesuchterString)) {
            return true;
        }
    }
    return false;
}
Alternativ gibts dafür auch schon etwas fertiges.
Java: 
Arrays.contains(array, "gesuchter String");
 
Ah ok, d.h. es wird dann jede Position im Array separat durchgegangen von oben nach unten? Also wird die binäre Suchfunktion nicht angewendet? 🙂
 
Achso, du wolltest das wieder mit der binären Suche machen.
Wenn du compareTo() verwendest, sollte das doch genauso funktionieren wie wir das bereits erarbeitet haben 🙂
 
Hey, danke für Deine Antwort!
Kann man denn die compareTo-Methode nicht einfach in den Code ganz oben einsetzen und vorher ein String-Array erstellen (statt wie bisher int)? Wir hatten ja in #13 den Code etwas umgeschrieben. Oder spricht da etwas gegen (längere Laufzeiten mal abgesehen)?
 
Also es scheitert im Quellcode an dem
Java: 
"array[mitte]< gesucht"
Da bei einem String nicht klar ist, was größer bzw. kleiner sein soll, stimmts? Allerdings ist der Code in #13 ja komplett anders als mein ursprünglicher?
 
Naja bei einem String ist schon klar welcher größer oder kleiner ist 🙂 Die werden lexikographisch verglichen. Und ja der Code in #13 ist anders. Versuche doch nochmal den Code mit deinen neuen Anforderungen zu schreiben.
 
Das finde ich relativ schwierig. An sich müsste ich doch mithilfe der compareTo-Methode nur
Java: 
String1.compareTo(array[mitte])
einfügen, oder? String1 ist der gesuchte String und das zu durchsuchende String-Array ist vorher durch
Java: 
String[] array = new String[] {"v", "w", "x", "y", "z"};
erstellt worden. Ist das der Ansatz?
 
Ah, ich hab es, es funktioniert 🙂 compareTo gibt offenbar einen int-Wert raus größer, gleich oder kleiner 0, oder?
Mit
Java: 
array[mitte].compareTo(String1)==0)
klappt es 🙂

Vielen Dank @ Jardcore 🙂
 
Achso, das ist dann dieser lexikografische Vergleich 🙂

Ich habe gerade bemerkt, dass dieser Algorithmus nur bei aufsteigend sortierten Arrays funktioniert, also solche, die von A-Z sortiert sind, nicht bei solchen, die von Z-A sortiert sind.
Wie könnte man es anstellen, dass auch absteigend sortierte Arrays den Algorithmus fehlerfrei durchlaufen?
 
Binäre Suche benötigt von Grund auf ein "sortiertes Array" und zwar "so sortiert", dass innerhalb der Binären Suche genau die Vergleichsfunktion genutzt wird, wie auch für die Sortierung.
 
Ok, danke für Deine schnelle Antwort. Das heißt, dass nicht derselbe Algorithmus für aufsteigend sortierte Arrays genutzt werden kann wie für absteigend sortierte Arrays, er also umgeschrieben werden müsste.

Könnte man denn eine Art "Erkennungsfunktion" einbauen, ob das Array auf- oder absteigend sortiert ist und dann entsprechenden Algorithmus anwenden?
 
Wenn du ein Comparable hast, also ein String o.Ä. dann könntest du z.b. das erste und letzte Element vergleichen, falls sie gleich sind, hast du nur gleiche Elemente -> fertig,
falls ersteres kleiner als letzeres ist das Array aufsteigend, sonst absteigend sortiert. Um die "andere" Sortierung zu erhalten, kannst du einfach das Vorzeichen deiner Vergleichsfunktion ändern.
 
Ah, das klingt einleuchtend!
Wie vergleiche ich denn, ob das erste Element größer ist als das letzte? Müsste der Code nicht in etwa so lauten?
Java: 
if (array [1] < [2]) {
           
        }
Und in den geschweiften Klammern dann der Suchalgorithmus. Jedoch scheint mir die if-Funktion wie eben beschrieben nicht zu funktionieren, greift man anders auf Elemente im Array zu?
 
@VfL_Freak: Ja, es gab einen Compilerfehler, deshalb wollte ich kurz nachfragen. Denselben Fehler gibt es auch mit Deiner Variante, weil es bei mir im Code ein String-Array ist. Der Compiler sagt dann "The Operator < ist undefined for the argument types java.lang.String"...
 
HO! hat gesagt.:
Ja, es gab einen Compilerfehler, deshalb wollte ich kurz nachfragen
Zum Vergrößern anklicken....
aha ... und warum postest Du ihn rsp. den kompletten StackTrace dann nicht ?? 😱

HO! hat gesagt.:
Denselben Fehler gibt es auch mit Deiner Variante, weil es bei mir im Code ein String-Array ist. Der Compiler sagt dann "The Operator < ist undefined for the argument types java.lang.String"...
Zum Vergrößern anklicken....
Ach so, String-Array (sorry, hatte den Rest nur überflogen) ...
na ja, Du kannst halt Strings nicht mit '<' oder '>' vergleichen (nur mit 'equals') !
Weiter oben wurde ja schon comparable erwähnt!

Worum geht es denn jetzt genau?
Um das Sortieren, um ein binäres Suchen?
oder ???

gruß Klaus
 
Also, es geht darum, dass ich gucken möchte, ob ein sortiertes String-Array auf- oder absteigend sortiert ist.
Ist es aufsteigend sortiert, soll Suchalgorithmus 1 durchlaufen werden. Ist es absteigend sortiert, soll Suchalgorithmus 2 durchlaufen werden.

Hierzu wollte ich das erste Element im String-Array mit dem letzten vergleichen:
Java: 
if(array[0].compareToIgnoreCase(array[array.length-1]) == 1)

Als Ergebnis/Rückgabewert habe ich ja entweder -1, 0 oder 1 und könnte so sehen, ob es auf- oder absteigend sortiert ist, oder?
 

Aktuelle Jobs

Neue Themen

Ähnliche Themen

Lineare Suche / Binäre Suche
Antworten: 2
Array, lineare Suche, binäre Suche, Programm bleibt unerwartet stehen...
Antworten: 6
Binäre-Suche Algorithmus
Antworten: 1
Binäre Suche
Antworten: 6
binäre Suche im Intervall
Antworten: 6

Zurück
Oben