Hallo Zusammen!

ich möchte mit Hilfe eines Struktogramms eine Binäre Suche in Java programmieren. Ich hab das ganze Strukto umsetzen könnne bis auf die eine Zeile...

Code java:

1	array[mitte] < suchwort

Man kann in Java keine Strings nach der größe vergleichen. Ich glaub mein Lehrer hat irgendwas wie einen Lexikalisches Verlgeich erwähnt gehabt (oder irgendwie so...).

Mein Programm sieht bis jetzt so aus

Code java:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

package BinäreSuche;   public class BinäreSuche {     private String[] array = {"Asterix", "Automatix", "Idefix", "Majestix", "Methusalix", "Miraculix", "Obelix"};     private int links = 0;     private int rechts = array.length - 1;     private int mitte = 0;     private String suchwort = "Miraculix";         public BinäreSuche(){         do{             mitte = (rechts + links) / 2;                         if(array[mitte] < suchwort){                 links = mitte + 1;             } else {                 rechts = mitte - 1;             }                         } while(array[mitte] != suchwort && links <= rechts);                 if(array[mitte].equals(suchwort)){             System.out.println("Position: " + mitte);         } else {             System.out.println("Suchwort nicht vorhanden!");         }     } }

Ich hoffe ihr könnt mir helfen!

MfG
Saban

Code java:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

package core;   public class BinaereSuche {     private String[] array = {             "Asterix", "Automatix", "Idefix", "Majestix", "Methusalix", "Miraculix", "Obelix"};     private int links = 0;     private int rechts = array.length - 1;     private int mitte = 0;     private String suchwort = "Miraculix";         public BinaereSuche()     {         do         {             this.mitte = (this.rechts + this.links) / 2;               if(array[mitte].length() < suchwort.length())                 this.links = mitte + 1;             else                 this.rechts = mitte - 1;         }         while(array[mitte] != suchwort && links <= rechts);                 if(this.array[this.mitte].equals(this.suchwort))             System.out.println("Position: " + this.mitte);         else             System.out.println("Suchwort nicht vorhanden!");     }     public static void main(String[] args)     {         new BinaereSuche();     } }

Aber warum nicht so?

Code java:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

package core;   public final class BinaereSuche extends Object {     private final String suchwort = "Miraculix";     private final String[] array =     {         "Asterix",         "Automatix",         "Idefix",         "Majestix",         "Methusalix",         "Miraculix",         "Obelix"     };         public BinaereSuche()     {         super();                 int result = -1;                 for(int i = 0; i < array.length; i++)             if(this.suchwort.equals(array[i]))             {                 result = i;                 break;             }               if(result != -1)             System.out.println("Position: " + (result + 1));         else             System.out.println("Nichts gefunden.");     }     public final static void main(String[] args)     {         new BinaereSuche();     } }

btw. was ist eine binäre Suche?
Und ein lexikalischer Vergleich?

€: OK, ich habe mal Miss Wiki gefragt, und deinen und meinen Source gegeneinander antrehten lassen. Laut System.nanoTime(); sind sie ziemlich genau gleich schnell.

Zitat von Kai008

Aber warum nicht so?

Weil eine binäre Suche viel schneller ist.

Zitat von Kai008

OK, ich habe mal Miss Wiki gefragt, und deinen und meinen Source gegeneinander antrehten lassen. Laut System.nanoTime(); sind sie ziemlich genau gleich schnell.

Wie hast du das denn gemessen? Mit den 5 Einträgen im Array? Und mit einem Durchlauf? Diese Messung kannst du getrost vergessen (mal abgesehen von der Genauigkeit von nanoTime()).

Die lineare Suche hat einen Aufwand O(n), die binäre Suche einen Aufwand von O(log n). Mit anderen Worten: binäre Suche ist um Längen schneller je mehr Elemente im Array sind.

Lexikalische Vergleiche kann man mit der String.compareTo Methode vollführen:

Code java:

1 2 3

if (array[mitte].compareTo(suchwort) < 0) {   ... }

Gruß

PS: @Saban: Deine Suche dürfte für ein leeres Array nicht funktionieren.

Hast recht.
Ich habs jetzt schnell mal mit 2000 Elementen gesucht.
Es enthielt immer nur A in der Länge des aktuellen Feldes + 1.
Also
A
AA
AAA
AAAA
usw.
Bei ihm kam 287437.
Bei mir 584162.
Also war meiner um 0.3ms langsamer, dennoch finde ich den Source um einiges übersichtlicher.
Und was genaueres als nanoTime() kenne ich leider in der Größenordnung nicht.

Die Methode verstehe ich irgendwie nicht. Laut Api vergleicht er einfach einen String mit einen Object, ist es kein String fliegt eine Exception?
Ich nehme dazu immer Klasse.class()/getClass und vergleiche sie per Equal.

Zitat von Kai008

Bei ihm kam 287437.
Bei mir 584162.
Also war meiner um 0.3ms langsamer

Man könnte auch sagen die binäre Suche war in dem Fall doppelt so schnell

Zitat von Kai008

, dennoch finde ich den Source um einiges übersichtlicher.

Also die Übersichtlichkeit leidet hierbei eigentlich noch nicht.

Zitat von Kai008

Und was genaueres als nanoTime() kenne ich leider in der Größenordnung nicht.

Das hängt von dem verfügbaren Timern der Plattform ab. Und wg. der Größenordnung läßt man den Algorithmus bei einem Benchmark üblicherweise gleich ein paar 100 Durchgänge laufen und ermittelt das arithm. Mittel.

Zitat von Kai008

Die Methode verstehe ich irgendwie nicht. Laut Api vergleicht er einfach einen String mit einen Object

Du hast die falsche Methode gegriffen. Die Methode ist überladen.

Gruß

Ups. OK, du hast recht, aber ich wüsste wiederrum nicht, wann man ein 2000-Felder-großes sortiertes Array rausbekommen sollte. Aber gut, jeder hat seine Art zu coden, aber bei 2000 würde ich schon versuchen eine HashMap anzulegen.
Aber ich finde es ehrlich gesagt schon unübersichtlich, dass er bei einzeiligen if's runde Klammern macht, deutsche Variablennamen verwendet, und keinen Pointer benutzt.

Durch die compareTo bin ich nun auf folgende Klasse gekommen:

Code java:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52

package core;   public final class Lexi extends Object {     private final String searchedString = "Miraculix";     private final String[] valueArray =     {             "Asterix",             "Automatix",             "Idefix",             "Majestix",             "Methusalix",             "Miraculix",             "Obelix"     };         public Lexi()     {         super();                 int cache = this.doSearch();         System.out.println(cache);     }     private final int doSearch()     {         int minValue = 0;         int maxValue = this.valueArray.length - 1;         int nowField = 0;         int loopResult = 0;         int result = -1;                 while(result == -1)         {             nowField = (int)Math.round((minValue + maxValue) / 2);             loopResult = this.searchedString.compareTo(this.valueArray[nowField]);               if(loopResult > 0 && nowField != minValue)                 minValue = nowField;             else if(loopResult < 0 && nowField != minValue)                 maxValue = nowField;             else if(loopResult == 0)                 result = nowField;             else                 break;         }               return(result);     }     public final static void main(String[] args)     {         new Lexi();     } }

Geschwindigkeit habe ich nicht getestet.
Ich finde, das ist noch um einiges besser lesbarer als alle vorherigen, und das geht imho über einen Geschwindigkeitsvorteil von ein paar µs, den man in der Regel sowieso nicht bemerken sollte.
Gefällt eventuell sogar deinen Lehrer@Saban.

Zitat von Kai008

Ups. OK, du hast recht, aber ich wüsste wiederrum nicht, wann man ein 2000-Felder-großes sortiertes Array rausbekommen sollte.

Wenn man Elemente sortiert in ein Array einfügt?! Ein Array mit 2000 Elementen ist doch gar nichts. Du solltest nicht von Spielzeugprogrammen ausgehen.

Zitat von Kai008

Aber gut, jeder hat seine Art zu coden, aber bei 2000 würde ich schon versuchen eine HashMap anzulegen.

Die ist dann aber nicht sortiert und man kann keine Duplikate einfügen...

Zitat von Kai008

Aber ich finde es ehrlich gesagt schon unübersichtlich, dass er bei einzeiligen if's runde Klammern macht

Du meinst die geschweiften Klammern? Die meisten IDEs setzen die Klammern automatisch und es ist absolut kein Problem.

Zitat von Kai008

deutsche Variablennamen verwendet

Gut, das ist vielleicht etwas extravagant.

Zitat von Kai008

und keinen Pointer benutzt.

Was meinst du mit Pointer?

Zitat von Kai008

Ich finde, das ist noch um einiges besser lesbarer als alle vorherigen, und das geht imho über einen Geschwindigkeitsvorteil von ein paar µs, den man in der Regel sowieso nicht bemerken sollte.

Du solltest nicht von so wenig Elementen bzw. nur von einem Suchlauf ausgehen.

Zitat von Kai008

Gefällt eventuell sogar deinen Lehrer@Saban.

Das glaube ich nicht. Es soll eine binäre Suche implementiert werden, so wie ich das verstanden habe.

Gruß

Warum, dass ist das unterste doch jetzt.

Zuerst wird das mittlere Element des Arrays überprüft. Es kann kleiner, größer oder gleich dem gesuchten Element sein. Ist es kleiner als das gesuchte Element, muss das gesuchte Element in der hinteren Hälfte stecken, falls es sich dort überhaupt befindet. Ist es hingegen größer, muss nur in der vorderen Hälfte weitergesucht werden. Die jeweils andere Hälfte muss nicht mehr betrachtet werden. Ist es gleich dem gesuchten Element, ist die Suche (vorzeitig) beendet.

Jede weiterhin zu untersuchende Hälfte wird wieder gleich behandelt: Das mittlere Element liefert wieder die Entscheidung darüber, wo bzw. ob weitergesucht werden muss.

Macht es doch alles. Bei jeden Schleifendurchlauf rücken minValue und maxValue weiter zusammen, und grenz so den Bereich weiter ein, in dem sich das Wort befinden könnte.

Ach ja, mit Pointer meinte ich "this".
Eine andere Frage, die ich mir jetzt gestellt habe ist: Wozu sucht man wo sich in einen Array ein Objekt befindet, wenn man das Objekt schon kennt? Aber gut, irgend eine Anwendungsmöglichkeit wirst du jetzt sich gleich parat haben. ^^

Zitat von Kai008

Eine andere Frage, die ich mir jetzt gestellt habe ist: Wozu sucht man wo sich in einen Array ein Objekt befindet, wenn man das Objekt schon kennt?

Weil man testen möchte, ob sich das Objekt überhaupt im Array befindet. Oder man sucht nur anhand eines Schlüssels, welcher die gesuchten Objekte identifiziert, aber nicht vollständig beschreibt (Beispiel: Suche in einem Telefonbuch nach Nachname).

Zitat von Kai008

Warum, dass ist das unterste doch jetzt.

Sorry, ich dachte du bist immer noch bei der linearen Suche.

Allerdings funktioniert dein Algorithmus auch nicht für ein leeres Array.

Gruß

PS: Noch eine Anmerkung. Was du hier machst:

Code java:

1	nowField = (int)Math.round((minValue + maxValue) / 2);

ist ziemlich unsinnig. Du berechnest ((minValue + maxValue) / 2. Alle Operanden sind Integer, d.h. das Ergebnis ist auch ein Integer. Dann rufst du Math.round auf, wobei der Integer automatisch in einen Float Wert konvertiert wird, und dann konvertierst du das Ergebnis wieder zurück zu int.

Hi Leute!

Tut mir leid das ich jetzt erst wieder Posten kann!

Aber Ich hab leider immer noch kein Post zu meinem Problem bekommen oder hab ich den übersehen?

MfG
Saban

Hi

Zitat von Saban

Aber Ich hab leider immer noch kein Post zu meinem Problem bekommen oder hab ich den übersehen?

Hast du wohl übersehen.

Gruß

Hi Saban,

hier haste deine Antworten (musst aber ein bisschen Englisch können):

http://java.sun.com/j2se/1.4.2/docs/...va.lang.String)

oder

http://java.sun.com/j2se/1.4.2/docs/.../Collator.html

musste dich mal ein bisschen durchfuchsen, ich glaube aber das erste sollte schon passen!

Danke für eure Hilfe!

Habs wirklich übersehen gehabt

MfG
Saban