Binary Search recursive: Wo liegt mein Fehler?

Bei Postings zu Aufgabe Nr. x = 1..4 lassen Sie Ihr Betreff bitte mit "x: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!

Moderator: Algorithmen und Datenstrukturen

Forumsregeln
Bei Postings zu Aufgabe Nr. x = 1..4 lassen Sie Ihr Betreff bitte mit "x: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!
Voleuro
Neuling
Neuling
Beiträge: 9
Registriert: 14. Mai 2017 15:21

Binary Search recursive: Wo liegt mein Fehler?

Beitrag von Voleuro » 9. Jun 2017 14:44

Hallo,

Ich habe mich jetzt schon einige male an der Aufgabe "Binary Search recursive" versucht. Bei mir laufen 10/12 Tests durch, ich kann aber nicht erkennen woran die restlichen zwei scheitern. Ich habe meinen Code auch in einer Programmierumgebung getestet und es scheint alles so zu funktionieren wie es soll. Von daher würde ich mich freuen, wenn jemand den Fehler findet. :)

Hier Ist der Code:

Code: Alles auswählen

public int binarySearchStep(Listobject<T>[] array, Listobject<T> searchedObject)
{
    if(array == null || searchedObject == null) {
        throw new NullPointerException();
    }
    
    if(array.length == 0) {
        return -1;
    }
    
    if(array.length == 1 && array[0].compareTo(searchedObject) != 0) {
        return -1;
    }
    
    int mid = (array.length)/2 ;
    int cmp = array[mid].compareTo(searchedObject);
    if(cmp == 0) {
        return mid;
    }
    else if(cmp > 0) {
        Listobject<T>[] partial = new Listobject[mid];
        for(int i=0;i<partial.length;i++) {
            partial[i] = array[i];
        }
        
        //arraycopyStarter(array,0,partial,0,mid);
        return binarySearchStep(partial,searchedObject);
    }
    else {
        Listobject<T>[] partial = new Listobject[mid];
        for(int i=0;i<partial.length;i++) {
            partial[i] = array[mid+i];
        }
        
        //arraycopyStarter(array,mid,partial,0,mid);
        return binarySearchStep(partial,searchedObject);
    }
}
Die Fehlermeldungen sind wie Folgt:
Testheadder –
staticTest_binarySearchStep_recursiv_Invariant_holds_SearchedObjectInArray(array.search.tests_binarysearch_recursive.BinarysearchTests_recursiv)
Message – Array is: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ] the searched key 2 is in the searchspace. index 4 has the first decision: key 4 is not the searched key 2 . You have made first decision at key: 2 expected:<5> but was:<2>
Testheadder – dynamic_binarySearchStep_recursiv_searchedObjectIsInArray(array.search.tests_binarysearch_recursive.BinarysearchTests_recursiv)
Message – testarray: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 ]. Searched object: key: 2 data: 2. Index of solution: 105. Index of result: 35. expected:<105> but was:<35>
Liebe Grüße,
Kai

goerlibe
Mausschubser
Mausschubser
Beiträge: 51
Registriert: 24. Apr 2017 19:22

Re: Binary Search recursive: Wo liegt mein Fehler?

Beitrag von goerlibe » 15. Jun 2017 19:51

schön, ich bin also nicht alleine...
Vielleicht findet ja noch jemand eine Lösung

goerlibe
Mausschubser
Mausschubser
Beiträge: 51
Registriert: 24. Apr 2017 19:22

Re: Binary Search recursive: Wo liegt mein Fehler?

Beitrag von goerlibe » 17. Jun 2017 11:50

Ich brauche immer noch Hilfe bei der Aufgabe...
Der folgende Code besteht nur einen Test nicht:

Code: Alles auswählen

{
    if (array.length == 0) return -1;
    if (array.length == 1) {
        if (array[0].compareTo(searchedObject) == 0) return 0;
        else return -1;
    }
    
    int middle = array.length /2;
    
    // !!! Use compare only once per binarySearchStep method call!!!
    int cmpMiddleSearched = array[middle].compareTo(searchedObject);
    
    // middle element is searchedObject
    if(cmpMiddleSearched == 0) return middle;
    
    // middle element is larger -> searchedObject is in left part
    if(cmpMiddleSearched > 0) {
        Listobject[] left = Listobject.factoryMethodListobjectTArray(middle);
        arraycopyStarter(array, 0, left, 0, left.length);
        //recursion on left half
        return binarySearchStep(left, searchedObject);
    }
    
    // middle element is smaller -> searchedObject is in right part
    else {
        Listobject[] right = Listobject.factoryMethodListobjectTArray(array.length - (middle +1));
        arraycopyStarter(array, middle +1, right, 0, right.length);
        //recursion on right half
        int result = binarySearchStep(right, searchedObject);
        return result == -1 ? -1 : result + middle +1;
    }
}

Die Fehlermeldung des Tests lautet:

Code: Alles auswählen

Testheadder
staticTest_binarySearchStep_recursiv_Invariant_holds_SearchedObjectInArray(array.search.tests_binarysearch_recursive.BinarysearchTests_recursiv)

Message
Array is: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ] the searched key 2 is in the searchspace. index 4 has the first decision: key 4 is not the searched key 2 . You have made first decision at key: 2 expected:<5> but was:<2>

Trace
java.lang.AssertionError: Array is: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ] the searched key 2 is in the searchspace. index 4 has the first decision: key 4 is not the searched key 2 . You have made first decision at key: 2 expected:<5> but was:<2> at org.junit.Assert.fail(Assert.java:88) at org.junit.Assert.failNotEquals(Assert.java:834) at org.junit.Assert.assertEquals(Assert.java:645) at array.search.tests_binarysearch_recursive.BinarysearchTests_recursiv.staticTest_binarySearchStep_recursiv_Invariant_holds_SearchedObjectInArray(BinarysearchTests_recursiv.java:87) ...
Das interpretiere ich folgendermaßen: Es wird die Zahl 2 gesucht, die auch am Index 2 enthalten ist.
Der Test geht nun davon aus, dass ich am Index 4 meine erste Entscheidung mache. Irgendwoher meint der Test jedoch zu wissen, dass ich meine erste Entscheidung an Stelle 2 mache. Und dann erwartet er 5, erhält jedoch 2?
Irgendwie passt das alles nicht so ganz zusammen....
Ist der Test also fehlerhaft implementiert, oder ist nur die Beschreibung des Tests falsch und der Fehler liegt bei mir? (übliches Problem auf CodeMonkeys, aber darüber wollen wir hier nicht auch noch reden)

gerigeri
Neuling
Neuling
Beiträge: 4
Registriert: 15. Jun 2017 14:37

Re: Binary Search recursive: Wo liegt mein Fehler?

Beitrag von gerigeri » 17. Jun 2017 13:05

Vergleich mal mit meinem Code:

Code: Alles auswählen

public int binarySearchStep(Listobject<T>[] array, Listobject<T> searchedObject)
{
    if (searchedObject == null || array == null) {
      throw new NullPointerException();
    }
    if(array.length < 1)
        return -1;
    
    int m = array.length / 2,
        c = searchedObject.compareTo(array[m]);
    if(array.length == 1 && c != 0)
        return -1;
    if(c == 0)
        return m;
    if (c > 0){
        int l = array.length - m - 1;
        Listobject<T>[] newArray = new Listobject[l];
        arraycopyStarter(array,m+1,newArray,0,l ) ;
        
        int k = binarySearchStep(newArray,searchedObject);
        return (k == -1)? -1: m+1 + k;
    }else{
        int l = array.length - m - ((array.length% 2 == 0)? 0:1);
        Listobject<T>[] newArray = new Listobject[l];
        arraycopyStarter(array,0,newArray,0,l) ;
        return binarySearchStep(newArray,searchedObject);
    }
}


Kabooom
Erstie
Erstie
Beiträge: 19
Registriert: 17. Jun 2017 15:04

Re: Binary Search recursive: Wo liegt mein Fehler?

Beitrag von Kabooom » 17. Jun 2017 15:18

Hallo Voleuro,

ich weiß leider auch nicht, was der Sinn des ersten Tests ist, aber er schlägt nicht mehr fehl wenn man statt

Code: Alles auswählen

int cmp = array[mid].compareTo(searchedObject);
das umgekehrt vergleicht

Code: Alles auswählen

int cmp = searchedObject.compareTo(array[mid]);
und dann die if-Bedingungen umdreht.

Beim zweiten Test ist dein Fehler wahrscheinlich, dass du den Index aus dem rechten Teilarray nicht korrekt berechnest: Wenn das Objekt im rechten Teilarray an Index i gefunden wurde, muss das Ergebnis mid+1+i sein.

goerlibe
Mausschubser
Mausschubser
Beiträge: 51
Registriert: 24. Apr 2017 19:22

Re: Binary Search recursive: Wo liegt mein Fehler?

Beitrag von goerlibe » 17. Jun 2017 17:07

danke, seit ich das mit dem compare umgedreht habe tut alles!
zwar nicht alles gleichzeitig aber immerhin, je nach Lust und Laune des Servers schaff ich zwischen 7 und 11 Tests, wobei aber jeder Test erfüllt wurde bei mehrmaligem Ausprobieren.

Liebe Tutoren - bitte kümmert euch um die Timeouts und darum, dass man compare auch anders rum anwenden darf (Zeitaufwand für diese Aufgabe: ca 2 Stunden dank nicht funktionierender Tests - ich dachte, der Fehler läge bei mir)

Julian Prommer
Moderator
Moderator
Beiträge: 167
Registriert: 17. Apr 2013 15:48

Re: Binary Search recursive: Wo liegt mein Fehler?

Beitrag von Julian Prommer » 19. Jun 2017 12:20

Timeouts werden nur hochgedreht, wenn das berechtigt ist.

Gründe für Timeouts sind eben auch Auslastung und bei starker Auslastung die Timeouts hochzudrehen macht nur alles schlimmer.
Solange nicht geklärt was die Timeouts so zum wackelt bringt, bleiben die halbwegs niedrig.

-> Wegen der Timeouts ist ein neues Feature im Test und ausprobierbar: Tests wiederholen nach dem ein Testat bereits beendet wurde, falls es nur der Serverauslastung lag hilft das schoneinmal. Es werden genau die Tests nochmal ausgeführt, welche zum Zeitpunkt des Testats vorlagen.
-> Weitere Features zur Selbsthilfe sind in Arbeit, aber werden komplizierter und 3-4 Wochen Entwicklung brauchen...
AuD Orga

Antworten

Zurück zu „AuD: Programmieraufgaben“