Binäre Suche, unsortiert, lokales Maximum

RudiRüssel

Mitglied
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.

Java:
//
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;
}
 

RudiRüssel

Mitglied
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

Top Contributor
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.
 

httpdigest

Top Contributor
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

Mitglied
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.
 

RudiRüssel

Mitglied
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

Java:
//
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];
    }
 
K

kneitzel

Gast
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.
 
Zuletzt bearbeitet von einem Moderator:

httpdigest

Top Contributor
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

Mitglied
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.

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.
 

PinkMuffin

Bekanntes Mitglied
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.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
M binäre Suche im Intervall Java Basics - Anfänger-Themen 6
M binäre Suche Java Basics - Anfänger-Themen 4
amelie123456 Lineare Suche / Binäre Suche Java Basics - Anfänger-Themen 2
K Warum ist die binäre Suche bei der verketteten Liste nicht so effektiv? Java Basics - Anfänger-Themen 3
S Binäre-Suche Algorithmus Java Basics - Anfänger-Themen 1
S Binäre-Suche bei unsortierten Daten Java Basics - Anfänger-Themen 7
L Binäre Suche mit Comparator Java Basics - Anfänger-Themen 5
H Erste Schritte Binäre Suche Java Basics - Anfänger-Themen 37
H Rekursion Binäre Suche Java Basics - Anfänger-Themen 2
L Binäre Suche Java Basics - Anfänger-Themen 2
N Array, lineare Suche, binäre Suche, Programm bleibt unerwartet stehen... Java Basics - Anfänger-Themen 6
B Binäre Suche - Junit Test Java Basics - Anfänger-Themen 6
J Binäre Suche eines Array Java Basics - Anfänger-Themen 5
M Methoden Binäre Suche als rekursive Variante Java Basics - Anfänger-Themen 5
B Binäre Suche in einem String Array Java Basics - Anfänger-Themen 10
M Binäre Suche Fehler überall =( Java Basics - Anfänger-Themen 2
D Binäre Suche für Integerarray in rekursiver Funktion Java Basics - Anfänger-Themen 5
W Compiler-Fehler Binäre Suche Java Basics - Anfänger-Themen 2
S Multi-Threaded Binäre Suche Java Basics - Anfänger-Themen 29
A Binäre Suche Java Basics - Anfänger-Themen 2
W Binäre Suche Java Basics - Anfänger-Themen 8
O String Binäre Suche Java Basics - Anfänger-Themen 6
M Binäre Suche, Elemente einfügen Java Basics - Anfänger-Themen 2
A Binäre Suche; Java Basics - Anfänger-Themen 6
pkelod Binäre Darstellung Bitwise-Operator Java Basics - Anfänger-Themen 10
Cassy3 Binäre Bäume Rekursiv durchlaufen und bestimmte Elemente Zählen Java Basics - Anfänger-Themen 6
S binäre semaphore Java Basics - Anfänger-Themen 4
Aprendiendo Gibt es in der JAVA-API eine Funktion, die eine Dezimalzahl in eine binäre Zahl umwandelt? Java Basics - Anfänger-Themen 8
A Binäre Addition Java Basics - Anfänger-Themen 15
V Binäre Suchbäume Java Basics - Anfänger-Themen 1
M Compiler-Fehler Binäre Zahlen in Dezimalzahlen umrechnen Java Basics - Anfänger-Themen 3
K binäre Suchbäume Java Basics - Anfänger-Themen 3
A Binäre Addition Java Basics - Anfänger-Themen 5
E Binäre Bäume Java Basics - Anfänger-Themen 7
0x7F800000 wie pack ich komplette objekte in binäre dateien? Java Basics - Anfänger-Themen 4
F Binäre Exponentiation Java Basics - Anfänger-Themen 9
M binäre Daten als Double einlesen Java Basics - Anfänger-Themen 22
M binäre daten einlesen Java Basics - Anfänger-Themen 2
G Binäre Suchbaum + Erstellung des Programmes Java Basics - Anfänger-Themen 4
R Binäre logische Operatoren Java Basics - Anfänger-Themen 21
I Reflection: Suche Feld + in Unterklassen Java Basics - Anfänger-Themen 7
LimDul Suche Java Stream Tutorial Java Basics - Anfänger-Themen 2
M Suche Resteasy Example Java Basics - Anfänger-Themen 24
B Beliebiger String gegeben Suche Datum in String Java Basics - Anfänger-Themen 6
H Suche Java3D 32 bit Java Basics - Anfänger-Themen 20
F Suche nach betreuender Person für eine Jahresarbeit der 12. Klasse. Java Basics - Anfänger-Themen 6
H Suche jemanden für kleine Uni-Abgabe/ mit Vergütung Java Basics - Anfänger-Themen 1
Y Suche von Studenten anhand Ihrer Eigenschaften. Java Basics - Anfänger-Themen 1
F Auf der Suche in π Java Basics - Anfänger-Themen 13
C Suche Nachhilfe in Java Java Basics - Anfänger-Themen 5
T Binärbaum-Suche Implementation Java Basics - Anfänger-Themen 6
A suche dringend Hilfe!! Java Basics - Anfänger-Themen 6
N Operatoren Schreibtischtest der Reihen-Suche nach Aufschluss in die Basics Java Basics - Anfänger-Themen 1
B Suche free SVN Hosting Java Basics - Anfänger-Themen 12
S Java Lineare-Suche Zeitmessung Java Basics - Anfänger-Themen 5
S Java Lineare Suche Java Basics - Anfänger-Themen 1
E Die richtige Suche in der API Java Basics - Anfänger-Themen 1
S suche nach varible POSITION ... fuer das pixel-maennchen Java Basics - Anfänger-Themen 4
E Weg-Suche-Problem rekursiv Java Basics - Anfänger-Themen 12
B Suche Programme mit Fehlern Java Basics - Anfänger-Themen 9
jaleda100 Component für Suche Java Basics - Anfänger-Themen 4
L Suche ein sampel Projekt Java Basics - Anfänger-Themen 2
P Suche Aufwandsgenerator (o-notation) Java Basics - Anfänger-Themen 1
S Suche aktuelles 2D Grafik Tutorial Java Basics - Anfänger-Themen 5
M Suche hilfe bei Array Java Basics - Anfänger-Themen 4
J Methoden Suche effiziente Implementierung für eine Methode Java Basics - Anfänger-Themen 3
D Ich suche nach einer Möglickeit den Webseiten Inhalt per Java zu analysieren Automatisch Java Basics - Anfänger-Themen 3
B String: suche nach Wörter und in List<String> speichern Java Basics - Anfänger-Themen 3
D Erste Schritte Suche Quelltext Java Basics - Anfänger-Themen 7
M Rekursion Minimums Suche Java Basics - Anfänger-Themen 12
J Suche Hilfestellung Java Basics - Anfänger-Themen 10
G Erste Schritte Suche Java Programmierer für kleines Projekt Java Basics - Anfänger-Themen 1
J Suche die Emailadresse Java Basics - Anfänger-Themen 6
H Suche in Text und Markierung Java Basics - Anfänger-Themen 14
H Suche in einem Text Java Basics - Anfänger-Themen 17
J Suche simples Beispiel für die EOFException Java Basics - Anfänger-Themen 1
L Linerae Suche in einem sortierten Array Java Basics - Anfänger-Themen 2
I Innerhalb einer Methode suchen und hinzufügen. Neues Objekt in Suche dann? Java Basics - Anfänger-Themen 8
L Einfache Lineare Suche Java Basics - Anfänger-Themen 7
D Suche nach der Anzahl von Zonen zwischen zwei Punkten Java Basics - Anfänger-Themen 2
M Benutzerdefinierte Suche in einem String - outofbounds Java Basics - Anfänger-Themen 7
X Best Practice SUCHE ein gutes Javabuch! (kein Anfang von 0) Java Basics - Anfänger-Themen 5
A Heap Space Error bei rekursiver Suche in Dateien trotz nur einer Zeile im Speicher Java Basics - Anfänger-Themen 26
M Rekursive Suche in einem Feld Java Basics - Anfänger-Themen 11
S Suche richtigen Typ für Variabel mit den Werten (neu, gebraucht, beschädigt) Java Basics - Anfänger-Themen 7
M Best Practice Programmierstil Graphen-A*-Suche Java Basics - Anfänger-Themen 5
M Suche Hilfe bei sehr kleinen Quelltexten Java Basics - Anfänger-Themen 2
E Suche Klasse die eine Bedinung prüft und einen von zwei Auswahlwerten zurückgibt... Java Basics - Anfänger-Themen 6
D Erste Schritte suche hilfe für db-anbindung Java Basics - Anfänger-Themen 36
S Java Servlet - Suche Java Basics - Anfänger-Themen 1
P Hashing suche Java Basics - Anfänger-Themen 4
K Suche Hilfe bei einfachem Java Code ( Debuggen ) Java Basics - Anfänger-Themen 1
J Variablen Auf der suche nach einem Befehl Java Basics - Anfänger-Themen 2
Farbenfroh Suche Übungsaufgaben: BinaryTree, Stack Java Basics - Anfänger-Themen 0
D Binärbaum Suche Java Basics - Anfänger-Themen 5
U Vererbung Suche Hilfe anhand eines Bsp. Java Basics - Anfänger-Themen 1
L Suche Programmier-Projekt mit Anleitung Java Basics - Anfänger-Themen 3
A Suche Programmierer für Android App Java Basics - Anfänger-Themen 1
H Suche Vergleichstabelle für die Klassen String und StringBuilder Java Basics - Anfänger-Themen 1
X [SUCHE]Mitentwickler Java Basics - Anfänger-Themen 10

Ähnliche Java Themen

Neue Themen


Oben