S
Spacerat
Gast
Hallo
Ich steh' grad' irgendwie auf dem Schlauch bei folgendem
Die Methode soll ein Objekt in eine sortierte Liste per Binärsuche einfügen. Das funktioniert soweit auch ganz gut, bis auf die Tatsache, dass vor dem ersten Element nichts eingefügt werden kann. Warum das so ist wird (wie man an den Versuchen mit min / max erkennen kann) mir nicht so ganz Klar. Sicher irgendeine Fanalität (fatale Banalität).
Um andere Lösungen mit vorhandenen Implementationen wie z.B. "Arrays.sort()", "TreeSet" oder per "verketteter Liste" auszuschliessen... Alles ausprobiert, mit den Ergebnissen:
- zu unperformant (verkettete Liste)
- zuviele temporäre Objekte (TreeSet)
- Objekte nicht "Comparable" (Arrays)
Ich steh' grad' irgendwie auf dem Schlauch bei folgendem
Code:
public void add(Object v)
{
int lo = 0;
int hi = size;
int pt = hi / 2;
boolean search = true;
while(search) {
switch(vc.compare(data[pt], v)) {
case 0:
System.arraycopy(data, pt + 1, data, pt + 2, size - pt - 1);
data[pt + 1] = v;
size++;
return;
case -1:
lo = pt;
pt += (hi - lo) / 2;
break;
case 1:
hi = pt;
pt -= (hi - lo) / 2;
break;
}
search = pt != hi && pt != lo;
}
pt = Math.max(lo, pt); /*Math.min(lo, pt);*/ /*Math.max(pt, hi);*/ /*Math.min(pt, hi);*/
System.arraycopy(data, pt, data, pt + 1, size - pt);
data[pt] = v;
size++;
}
Um andere Lösungen mit vorhandenen Implementationen wie z.B. "Arrays.sort()", "TreeSet" oder per "verketteter Liste" auszuschliessen... Alles ausprobiert, mit den Ergebnissen:
- zu unperformant (verkettete Liste)
- zuviele temporäre Objekte (TreeSet)
- Objekte nicht "Comparable" (Arrays)
Zuletzt bearbeitet von einem Moderator: