Binäre Suche, unsortiert, lokales Maximum

[RudiRüssel]

Hallo liebes Forum.
Da ich Anfänger bin und fleißig für meine Prüfung lerne habe ich mich an einem etwas kniffligen Beispiel versucht. Gegeben ist ein array mit den Zahlen {36, 42, 24, 18, 12, 6, 24, 30}. Nun soll ich die Binäre Suche mithilfe von binarySearch(int[] x) angehen. Gesucht wird ein lokales Maximum. Dh es könnte theoretisch 42 sein, oder auch 30.

Nun zu meinem Ansatz (nicht vergessen ich bin Anfänger, weswegen auch leicht vermeidbare/offensichtliche Fehler auftreten können). Die Ausgabe die ich erhalte ist 18. Was leider total falsch ist... Hoffe mir kann jemand helfen.

//
int binarySearch(int[] x) {
    int Ug = 0;
    int Og = x.length-1;

    while(Ug <= Og) {
        int mitte = (Og+Ug)/2;
     
        if (Ug < x[mitte] && Og < x[mitte]){
            return x[mitte];  
        }
        else if (mitte-1 >= 0 && zahlen[mitte] < zahlen[mitte-1]) {
            Og = mitte-1;
            continue;
        }
        else {
            Ug = mitte+1;
            continue;
        }
    }
    return -1;
}

 

[httpdigest]

Binärsuche funktioniert nur, wenn das zu durchsuchende Array sortiert ist.

 

[RudiRüssel]

Also bedeutet das, dass ich mir das ganze sparen kann und einfach den array mit sort() sortiere und dann auf das letzte Element 42 zugreife? Danke schonmal.

 

[httpdigest]

Naja, die Frage ist auch, was du mit "lokales Maximum" meinst... also was daran "lokal" sein soll und nicht einfach das Maximum der Elemente in dem Array. Da kannst du natürlich einfach einmal durch das Array gehen (ohne zu sortieren) und dir das jeweils maximale Element merken.

 

[RudiRüssel]

Naja, die Frage ist auch, was du mit "lokales Maximum" meinst... also was daran "lokal" sein soll und nicht einfach das Maximum der Elemente in dem Array.

Man muss es so sehen wie es ungeordnet dort steht. Dann erkennt man lokale Maxima im Falle wären das 30 oder 42 🙂

 

[httpdigest]

Man muss es so sehen wie es ungeordnet dort steht. Dann erkennt man lokale Maxima im Falle wären das 30 oder 42 🙂

Das verstehe ich nicht. Wo fängt denn ein "lokal" an und wo hört ein "lokal" auf?? Und warum sind es dann zwei Maxima und nicht 8?

 

[RudiRüssel]

Die Definition was ein lokales Maximum ist liefert dir die Antwort 😀

 

[httpdigest]

Binärsuche kann man verwenden, um in einem sortierten Array ein ganz bestimmtes/gegebenes Element zu finden. Also z.B. einfach das Element 30.
Wenn du jetzt sagst, du willst ein "lokales" Maximum finden, dann ist das kein konkretes/gegebenes Element, sondern eine Funktion bzw. ein Prädikat, welches für das zu suchende Element erfüllt werden soll.

Dann also formal die Aufgabenstellung:
"Gegeben eine Liste mit (gemäss dem "<=" Operator) unsortierten/ungeordneten Elementen. Finde das lokale Maximum."

Wie würdest du das denn tun, bzw. wie interpretierst du denn das Prädikat "lokales Maximum"?

 

[RudiRüssel]

Binärsuche kann man verwenden, um in einem sortierten Array ein ganz bestimmtes/gegebenes Element zu finden. Also z.B. einfach das Element 30.
Wenn du jetzt sagst, du willst ein "lokales" Maximum finden, dann ist das kein konkretes/gegebenes Element, sondern eine Funktion bzw. ein Prädikat, welches für das zu suchende Element erfüllt werden soll.

Dann also formal die Aufgabenstellung:
"Gegeben eine Liste mit (gemäss dem "<=" Operator) unsortierten/ungeordneten Elementen. Finde das lokale Maximum."

Wie würdest du das denn tun?

Ich wusste ja nichtmal, dass man bei binärer Suche sortieren muss. Du musst denke ich einfach (obwohl du sortierst) dir im Kopf behalten, welche Werte im Graphen die lokalen Maxima waren. Warte ich schreib es neu.

 

[httpdigest]

Du musst denke ich einfach (obwohl du sortierst) dir im Kopf behalten, welche Werte im Graphen die lokalen Maxima waren.

Was denn nun wieder für ein Graph?

 

[RudiRüssel]

Was denn nun wieder für ein Graph?

Warum ist das so schwer zu verstehen.. der Graph war nur ein bildliches Beispiel für die Zahlen... aber danke für die Hilfe

//
int binarySearch(int[] arr){
        int lowest = 0;
        int highest = arr.length-1;
        int [] arrShort;
        int middle = (lowest+highest)/2;

            if (middle - 1 >= 0 && arr[middle] < arr[middle - 1]) {
                highest = middle - 1;
            }
            arrShort = new int[highest + 1];

            for (int i = 0; i < highest + 1; i++) {
                arrShort[i] = arr[i];
            }
            Arrays.sort(arrShort);

                return arrShort[arrShort.length-1];
    }

 

[kneitzel]

Also die Aufgabe ist sehr wirr und so nicht wirklich zu verstehen.

Binary Suche bedeutet, dass Du in einer sortierten Menge in die Mitte gehst und dann mit dem Vergleich feststellst, ob Du rechts oder links weiter suchen musst. Das ist dann eine sehr schnelle suche (O(log(n)), aber das setzt natürlich voraus, dass das Array sortiert ist.
https://de.wikipedia.org/wiki/Binäre_Suche

Lokales Maxima - das ist ein Element, welches rechts und link ein kleineres Element hat. Das besagt nichts darüber aus, ob es das größte Element ist oder nicht ...

Du läufst also so lange durch das Array, bis du bei einem Element bist, dessen Nachfolger kleiner ist oder es keinen Nachfolger gibt.
Beispiel 12, 11, .... => 12 ist ein lokales Maximum ...
Beispiel 3, 4, 5, 2, ... => 5 ist ein lokales Maximum ...
Beispiel: 1, 2, 3, 4, 5 -> 5 ist ein lokales Maximum (und zugleich das größte Maximum).
Da hast Du also einen einfachen Algorithmus um ein lokales Maximum zu finden. Also auch nichts wildes. Aber hat mit einer binären Suche absolut nichts zu tun!

Und dann - als wäre das noch nicht genug Verwirrung in einer Aufgabe, bringst Du noch Graphen. Die Zahlen können irgend für irgend was stehen. Das ist erst einmal für die Aufgabe egal. Da können das die Scheißhaufen Deiner Hunde sein, die diese pro Tag auf eurem Grundstück abgelegt haben oder das Taschengeld von Dir oder oder oder ... Das spielt für diese Aufgabe vollkommen keine Rolle. Egal für was diese Zahlen stehen: Suche und lokales Maxima oder so verändern sich nicht ...

Also kann es auch für einen Graphen stehen. Aber da bräuchte man dann wohl etwas mehr Informationen. Da wäre aber wichtig, dass Du die Informationen, die für die Aufgabe wichtig sind, verständlich formuliert rüber bringst.

 

[httpdigest]

Warum ist das so schwer zu verstehen.. der Graph war nur ein bildliches Beispiel für die Zahlen...

Weil du es bisher nicht vernünftig, formal und insbesondere eindeutig erklärt hast. Wie soll man denn bitte in einer Liste von unsortierten Zahlen einen Graphen erkennen? Was soll denn da überhaupt was sein?
Du scheinst aktuell einfach sehr viel implizites Wissen bzw. implizite Annahmen zu treffen, die aktuell sonst keiner mit dir teilt bzw. von denen keiner weiss.

 

[RudiRüssel]

Also die Aufgabe ist sehr wirr und so nicht wirklich zu verstehen.

Binary Suche bedeutet, dass Du in einer sortierten Menge in die Mitte gehst und dann mit dem Vergleich feststellst, ob Du rechts oder links weiter suchen musst. Das ist dann eine sehr schnelle suche (O(log(n)), aber das setzt natürlich voraus, dass das Array sortiert ist.

Binäre Suche – Wikipedia

de.wikipedia.org

Lokales Maxima - das ist ein Element, welches rechts und link ein kleineres Element hat. Das besagt nichts darüber aus, ob es das größte Element ist oder nicht ...

Du läufst also so lange durch das Array, bis du bei einem Element bist, dessen Nachfolger kleiner ist oder es keinen Nachfolger gibt.
Beispiel 12, 11, .... => 12 ist ein lokales Maximum ...
Beispiel 3, 4, 5, 2, ... => 5 ist ein lokales Maximum ...
Beispiel: 1, 2, 3, 4, 5 -> 5 ist ein lokales Maximum (und zugleich das größte Maximum).
Da hast Du also einen einfachen Algorithmus um ein lokales Maximum zu finden. Also auch nichts wildes. Aber hat mit einer binären Suche absolut nichts zu tun!

Und dann - als wäre das noch nicht genug Verwirrung in einer Aufgabe, bringst Du noch Graphen. Die Zahlen können irgend für irgend was stehen. Das ist erst einmal für die Aufgabe egal. Da können das die Scheißhaufen Deiner Hunde sein, die diese pro Tag auf eurem Grundstück abgelegt haben oder das Taschengeld von Dir oder oder oder ... Das spielt für diese Aufgabe vollkommen keine Rolle. Egal für was diese Zahlen stehen: Suche und lokales Maxima oder so verändern sich nicht ...

Also kann es auch für einen Graphen stehen. Aber da bräuchte man dann wohl etwas mehr Informationen. Da wäre aber wichtig, dass Du die Informationen, die für die Aufgabe wichtig sind, verständlich formuliert rüber bringst.

Es hat auch keiner gesagt, dass ich das größte finden muss, sonder EIN lokales Maximum. Ich wusste einfach nur nicht, dass ich sortieren muss, damit hat sich das dann eh erledigt.

 

[httpdigest]

Und schon wieder fehlt die genaue Definition, was du denn unter einem lokalen Maximum (Plural ist Maxima) ganz genau verstehst.

 

[PinkMuffin]

Es hat auch keiner gesagt, dass ich das größte finden muss, sonder EIN lokales Maximum. Ich wusste einfach nur nicht, dass ich sortieren muss, damit hat sich das dann eh erledigt.

Wieso denn sortieren? Du kannst kein lokales Maximum finden, wenn du sortierst, weil bei einem lokalen Maximum die Umgebung entscheidend ist.
Wenn du nur eines willst, dann mach es wie @kneitzel beschrieben hat und brich einfach direkt ab, sobald du eines gefunden hast. Wird kein Element gefunden, auf das ein kleineres folgt, dann ist der Graph monoton steigend und dein letztes Element ist das absolute Maximum.
Allerdings müsstest du allgemein eine Richtungsänderung prüfen, sonst denkt der Algorythmus noch, bei einem monoton fallenden Graphen wäre jeder Wert ein lokales Maximum.