Codemonkeys: Binary Search

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!

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!
Benutzeravatar
sqrt(2)
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 202
Registriert: 12. Apr 2015 11:35

Codemonkeys: Binary Search

Beitrag von sqrt(2) » 26. Aug 2016 10:37

Hallo,

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

Benutzeravatar
luedecke
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 124
Registriert: 17. Mär 2015 00:08

Re: Codemonkeys: Binary Search

Beitrag von luedecke » 27. Aug 2016 09:28

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

Benutzeravatar
sqrt(2)
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 202
Registriert: 12. Apr 2015 11:35

Re: Codemonkeys: Binary Search

Beitrag von sqrt(2) » 27. Aug 2016 12:29

Okay, danke (:

joerg
Erstie
Erstie
Beiträge: 14
Registriert: 21. Sep 2015 19:15

Re: Codemonkeys: Binary Search

Beitrag von joerg » 28. Aug 2016 10:46

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
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 162
Registriert: 22. Apr 2015 19:03

Re: Codemonkeys: Binary Search

Beitrag von Hallo » 29. Aug 2016 16:40

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
Neuling
Neuling
Beiträge: 6
Registriert: 4. Sep 2016 17:30

Re: Codemonkeys: Binary Search

Beitrag von arman » 12. Sep 2016 15:50

15 Tests, wer bietet mehr? :lol:

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

Benutzeravatar
Malou
Windoof-User
Windoof-User
Beiträge: 26
Registriert: 19. Jun 2016 17:54

Re: Codemonkeys: Binary Search

Beitrag von Malou » 14. Sep 2016 17:21

16 Tests! 8)

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

Antworten

Zurück zu „AuD: Arbeit mit Nabla“