Codemonkeys: Binary Search
Moderator: Algorithmen und Datenstrukturen
Forumsregeln
Bei Postings zu Algorithmus X lassen Sie Ihren Betreff bitte mit
"X: " beginnen, bei allgemeinen Postings zu Nabla bitte mit "Nabla: ", jeweils gefolgt von einer möglichst präzisen Überschrift, danke!
Bei Postings zu Algorithmus X lassen Sie Ihren Betreff bitte mit
"X: " beginnen, bei allgemeinen Postings zu Nabla bitte mit "Nabla: ", jeweils gefolgt von einer möglichst präzisen Überschrift, danke!
Codemonkeys: Binary Search
Hallo,
wie erfolgt hier der Vergleich? Auch mit getComp().compare(x,y) wie in der Aufgabe Find Second Largest Element?
wie erfolgt hier der Vergleich? Auch mit getComp().compare(x,y) wie in der Aufgabe Find Second Largest Element?
Re: Codemonkeys: Binary Search
Habe ich jetzt durch einfaches durchlesen der Aufgabe auch nicht herausgefunden.
Habe demnach in die Referenzlösung geschaut und folgendes gefunden:
Ich gehe dann mal motzen...
Habe demnach in die Referenzlösung geschaut und folgendes gefunden:
Code: Alles auswählen
element.compareTo(element.getKey()) // returns int
Re: Codemonkeys: Binary Search
Okay, danke (:
Re: Codemonkeys: Binary Search
Hallo,
mit diesem Code komme ich durch 11 Tests durch. Leider werden ganz viele Elemente nicht gefunden, daher muss irgendwo ein grober Fehler sein...
Wäre über einen Tipp sehr dankbar...
mit diesem Code komme ich durch 11 Tests durch. Leider werden ganz viele Elemente nicht gefunden, daher muss irgendwo ein grober Fehler sein...
Wäre über einen Tipp sehr dankbar...
Code: Alles auswählen
{
if ( list == null || element == null){
lrm[2] = -1;
return lrm;
}
if (list.length == 1){
lrm[2] = 0;
return lrm;
}
while (lrm[0] <= lrm[1]){
lrm[2] = (lrm[0] + lrm[1]) / 2;
if (list[lrm[2]].compareTo(element.getKey()) == 0 ){
return lrm;
} else if (list[lrm[2]].compareTo(element.getKey()) == -1) {
lrm[0] = lrm[2] +1;
lrm[2] = (lrm[0] + lrm[1]) / 2;
}
else if (list[lrm[2]].compareTo(element.getKey()) == 1) {
lrm[1] = lrm[2] -1;
lrm[2] = (lrm[0] + lrm[1]) / 2;
}
}
return lrm;
}
Re: Codemonkeys: Binary Search
Mein Code sieht auch ganz ähnlich aus, kann aber nur durch 13 Tests.
Hast du deins schon korrigiert?
Hast du deins schon korrigiert?
Code: Alles auswählen
{
if(list==null || element == null){
lrm[2]= -1;
return lrm;
}
lrm[1]=list.length-1;
lrm[2]= (list.length-1) /2;
int l = lrm[0];
int r = lrm[1];
int m = lrm[2];
while(l <= r){
lrm[0]=l;
lrm[1]=r;
lrm[2]=m;
if(list[m].compareTo(element.getKey()) == 0){
return lrm;
}
if(m ==r && m==l){
if(list[m].compareTo(element.getKey()) == 0){
return lrm;
}
lrm[2]=-1;
return lrm;
}
else if(list[m].compareTo(element.getKey()) > 0){
r = m-1;
m= (l+r)/2;
}
else if(list[m].compareTo(element.getKey()) < 0){
l = m+1;
m= (l+r)/2;
}
}
return lrm;
}
Re: Codemonkeys: Binary Search
15 Tests, wer bietet mehr?

Code: Alles auswählen
{
if(list == null || element == null)
return lrm;
int low = lrm[0];
int high = lrm[1];
int mid = lrm[2];
while (low<=high) {
mid = (low + high) / 2;
int cmp = list[mid].compareTo(element.getKey());
if(cmp < 0) {
low = mid + 1;
}
else if (cmp > 0) {
high = mid - 1;
}
else {
break;
}
mid = -1;
}
lrm[0]=low;
lrm[1]=high;
lrm[2]=mid;
return lrm;
}
Re: Codemonkeys: Binary Search
16 Tests!

Code: Alles auswählen
{
// Falls die Liste oder das Element null ist, liefert -1 zurück.
if(list == null || element == null){
lrm[2] = -1;
return lrm;
}
// lrm[2] auf die Mitte des Teilarrays setzen.
lrm[2] = (lrm[0] + lrm[1])/2;
int cmp = list[lrm[2]].compareTo(element.getKey());
// Falls left = right = middle, liefert -1 falls das Element nicht enthalten
// ist und das Index des gesuchten Element ansonsten.
if(lrm[0]==lrm[1]){
if(cmp != 0){
lrm[2] = -1;
}
return lrm;
}
// Falls das element grösser als das mittlere ist, setze das linke Index
// auf Mitte + 1. Ansonsten wird das rechte Index auf Mitte -1 gesetzt.
if(cmp<0){
lrm[0] = lrm[2]+1;
}
else if(cmp>0){
lrm[1] = lrm[2]-1;
}
return lrm;
}