✔ Binäre Suche Java

[Saban]

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

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

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

 

[Kai008]

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?

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.

 

[deepthroat]

Aber warum nicht so?

Weil eine binäre Suche viel schneller ist.

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, 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:

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

Gruß

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

 

[Kai008]

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.

 

[deepthroat]

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 ;-]

, dennoch finde ich den Source um einiges übersichtlicher.

Also die Übersichtlichkeit leidet hierbei eigentlich noch nicht.

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.

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ß

 

[Kai008]

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:

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.

 

[deepthroat]

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.

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

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.

deutsche Variablennamen verwendet

Gut, das ist vielleicht etwas extravagant.

und keinen Pointer benutzt.

Was meinst du mit Pointer?

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.

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ß

 

[Kai008]

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

 

[Matthias Reitinger]

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

 

[deepthroat]

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:

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.