Binäre Suche

[Wang]

Hallo,

mir gelingt es nicht, einen Teil des folgenden Code-Fragments nachzuvollziehen:

int Binsearch (int[] A, int x)
{
int m = 0, u = 0, o = A.length - 1;
boolean gefunden = false;
while ((u <= o) && (!gefunden))
	{
	m = (u + o) / 2;
	if (x == A[m]) gefunden = true; // x gefunden an der Stelle m
	else if (x <= A[m]) o = m - 1; else u = m + 1;
	} // end while
if (!gefunden) return -1;
else return m;
}

Mein Problem ist das "!gefunden".
gefunden wird zu Beginn ja mit dem Wahrheitswert "false" initialisiert. Dann bedeutet doch "!gefunden", dass die Bedingung erfüllt ist, wenn gefunden nicht falsch, also wahr ist?

Wenn nun ein Element im Array gefunden worden ist, wird der Variable "gefunden" der Wahrheitswert "true" zugewiesen.
Ich sehe aber nicht, in welcher Weise "!gefunden" hier eine wichtige Rolle spielt bzw. als Abbruchbedingung dient?

Bitte dringend um Hilfe.

Vielen Dank.

Gruß
Wang

 

[srea]

...
while ((u <= o) && (!gefunden)) // 
...

Hi,

die Zeile beudeutet, steige in die Schleife ein, solange u kleiner/gleich o und gefunden = false ist. Wenn du bei A[m] aber x gefunden hat, wird [c]gefunden = true[/c] gesetzt, somit wird die Schleife nach dem Durchlauf abgebrochen.

 

[gman]

Hi,

du kannst es auch einfach umdrehen:

[JAVA=11]
if (gefunden)
return m;
else
return -1;
}
[/code]

So liest sich das doch gleich viel besser: "Wenn <gefunden> irgendwann mal auf <true> gesetzt wurde,
dann gebe <m> als Ergebnis zurück und sonst -1".

PS: Wenn man eine vernünftige IDE benutzt kann man auch vorher einfach mal ein wenig Refactoring
betreiben:

    public int binsearch(int[] array, int gesucht) {
        int median = 0, erstes = 0, letztes = array.length - 1;
        boolean gefunden = false;

        while ((erstes <= letztes) && (!gefunden)) {
            median = (erstes + letztes) / 2;
            if (gesucht == array[median]) {
                gefunden = true;
            } else if (gesucht <= array[median]) {
                letztes = median - 1;
            } else {
                erstes = median + 1;
            }
        }

        if (gefunden) {
            return median;
        } else {
            return -1;
        }
    }

 

[Wang]

Vielen Dank.

Das Problem war, dass ich "!gefunden" falsch interpretiert habe (anstatt "!gefunden" als "falsch" zu interpretieren, dachte ich es meint eine Negation der eingangs mit "false" initialisierten Variable "gefunden", also Bedingung erfüllt wenn "true".

Gruß
Wang

 

[Wang]

Eine Frage habe ich doch noch zu diesem Code:
Warum ist es nicht nötig,

int u = 0

zu schreiben?

Thanks

 

[srea]

int m = 0, u = 0, o = A.length - 1;

Steht doch da?

 

[Wang]

int m = 0, u = 0, o = A.length - 1;

Steht doch da?

Ich war mit meiner Frage zu ungenau... Ich wundere mich, warum es genügt

u = 0

anstatt

int u = 0

zu schreiben?

 

[Gast2]

int m = 0, u = 0, o = A.length - 1;

ist das selbe wie:

int m = 0;
int u = 0;
int o = A.length - 1;

Das int am Anfang der Zeile gilt für alle Variablen in der Zeile.

 

[Wang]

Vielen Dank, jetzt dämmert es mir wieder... :shock:
Vor lauter SML und SPIM in diesem Semester ist JAVA stark vernachlässigt worden.