Codemonkeys: Binary Search

[sqrt(2)]

Hallo,

wie erfolgt hier der Vergleich? Auch mit getComp().compare(x,y) wie in der Aufgabe Find Second Largest Element?

[luedecke]

Habe ich jetzt durch einfaches durchlesen der Aufgabe auch nicht herausgefunden.

Habe demnach in die Referenzlösung geschaut und folgendes gefunden:

Code: Alles auswählen

element.compareTo(element.getKey()) // returns int 

Ich gehe dann mal motzen...

[sqrt(2)]

Okay, danke (:

[joerg]

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

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

[Hallo]

Mein Code sieht auch ganz ähnlich aus, kann aber nur durch 13 Tests.

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

[arman]

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

[Malou]

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