Seite 1 von 1

Fehler in ex05 Aufgabe 1) ?

Verfasst: 30. Nov 2009 16:45
von naibaF
Hallo,

ich beziehe mich auf die Beschreibung von param upperBound von ArrayInserter.java:
Hence, if you want to search for a value in an entire Array upperBound has to be equal to <code>a.length-1</code>.
upperBound müsste doch aber a.length entsprechen um das ganze Array zu durchsuchen?

Re: Fehler in ex05 Aufgabe 1) ?

Verfasst: 30. Nov 2009 17:14
von mister_tt
Richtig - das denken wir auch.

Re: Fehler in ex05 Aufgabe 1) ?

Verfasst: 30. Nov 2009 19:13
von mitschke
Hallo,
Der Kommentar ist insofern korrekt, da die Methode mir zurückgibt wo im Array ich ein Element einfügen muß, damit das Array sortiert bleibt. Wenn also alle Elemente kleiner sind, werde ich am Ende einfügen müssen. In diesem Fall ist mir als Nutzer der Methode auch egal, ob der Wert dort schon gespeichert ist, da ich keinen doppelten Eintrag erzeugen werde.

Suchtechnisch gesehen, ist die mathematische Notation, die davor im Kommentar steht korrekt.
specify an upper bound to limit the search to the range [0..upperBound)
Wenn ich wirklich rausbekommen möchte, ob das Element schon im Array enthalten ist, stimmt es, dass ich upperBound=array.lenght mitgeben muß.
Dann ist die range [0..array.length) , was in unserem Fall äquivalent ist zu [0..array.length-1]

Re: Fehler in ex05 Aufgabe 1) ?

Verfasst: 30. Nov 2009 19:32
von naibaF

Code: Alles auswählen

int[] a = {0,2,4,6};
int ausgabe = ArrayInserter.getInsertionIndex(a, 3, 7);
System.out.println(ausgabe);
beispielsweise liefert mir doch aber 3 zurück. Das ist doch aber nicht korrekt da an Index 3 bereits 6 steht.

Re: Fehler in ex05 Aufgabe 1) ?

Verfasst: 30. Nov 2009 22:27
von eichberg
Das Array a hat 4 Einträge, der erste Array Eintrag liegt immer an Stelle 0... upperBound gibt den Index des letzten Elements an bis zu dem untersucht werden soll. In diesem Fall ist die upperBound = "3" = "a.length/*4*/-1".

Verkürztes Beispiel:
a={0,6}
getInsertionIndex(a,1,7)
=>
max_index = 1
min_index = 0
... (1. Schleifendurchlauf)
index = (min_index + max_index) / 2 = 0
v = a[0] = 0
if (value > v) /* 7 > 0 */
min_index = 1
... (2. Schleifendurchlauf)
index = 1
v = 6
if (value > v) /* 6 > 0 */
min_index = 2
...
return min_index/*!!!*/ = 2

Re: Fehler in ex05 Aufgabe 1) ?

Verfasst: 2. Dez 2009 19:31
von naibaF
eichberg hat geschrieben:Das Array a hat 4 Einträge, der erste Array Eintrag liegt immer an Stelle 0... upperBound gibt den Index des letzten Elements an bis zu dem untersucht werden soll. In diesem Fall ist die upperBound = "3" = "a.length/*4*/-1".

Verkürztes Beispiel:
a={0,6}
getInsertionIndex(a,1,7)
=>
max_index = 1
min_index = 0
... (1. Schleifendurchlauf)
index = (min_index + max_index) / 2 = 0
v = a[0] = 0
if (value > v) /* 7 > 0 */
min_index = 1
... (2. Schleifendurchlauf)
index = 1
v = 6
if (value > v) /* 6 > 0 */
min_index = 2
...
return min_index/*!!!*/ = 2
Um einen 2. Schleifendurchlauf zu haben müsste doch weiterhin min_index < max_index gelten.
Hier ist aber vor dem 2. Schleifendurchlauf min_index = max_index.

Oder sehe ich das falsch?

Re: Fehler in ex05 Aufgabe 1) ?

Verfasst: 3. Dez 2009 13:26
von eichberg
Sie haben recht (der Kommentar ist falsch... im Originalcode ist der Kommentar so, wie von Ihnen beschrieben, beim Übertragen ist wohl der Fehler unterlaufen.)