Wenn die Aussage wahre Bedingungen nicht erkennt?

Question

Ich habe Probleme mit diesem binären Suchalgorithmus. Hier sind Erklärungen der Variablen.

Wert: Die Zahl innerhalb des Arrays

Werte [] durchsucht wird: das Array, das

n durchsucht wird: Anzahl der Elemente in dem Array

hoch: höchste Element (durch Null indexierte Position) des Teils des Arrays durchsucht

niedrig: niedrigste Element (von Null indiziert Position), um den Teil des Arrays durchsucht werden

Mein Problem ist nicht die Rekursion. Der Teil des Arrays, der durchsucht wird, dreht sich um den "Wert" und die unten angegebenen Bedingungen werden erfüllt. Das Problem ist, dass meine if-Anweisungen das nicht zu erkennen scheinen. Ich weiß, dass die Bedingungen erfüllt sind, denn wenn ich für jede Rekursion Werte [hoch], Werte [Mitte] und Werte [niedrig] ausdrücke, zeigt dies an, dass sie es sind.

int search(int value, int values[], int n, int high, int low) 
{ 
    if (n <= 0) 
    { 
    return 1; 
    } 

    int middle = (high + low)/2; 

    ///condition #1 
    if (value == values[middle]) 
    { 
    return 0; 
    } 

    //conditions #2 and #3 (account for the maxes and mins of the array because the operation to find middle truncates) 
    else if (values[middle]==values[low] || values[middle]==values[high]) 
    { 
    return 0; 
    } 

    else if (value > values[middle]) 
    { 
     low = middle; 
     search(value, values, n, high, low); 
    } 

    else if (value < values[middle]) 
    { 
     high = middle; 
     search(value, values, n, high, low); 
    } 

    return 2; 
    } 

Was ist hier falsch?

Answer 1

Betrachten Sie nah diesem Code:

else if (value > values[middle]) 
{ 
    low = middle; 
    search(value, values, n, high, low); 
} 

else if (value < values[middle]) 
{ 
    high = middle; 
    search(value, values, n, high, low); 
} 

Beachten Sie, dass in diesen Fällen rufen Sie die search Funktion rekursiv, aber sie tun nichts mit dem Rückgabewert. Dies bedeutet, dass der Wert, der von search zurückgegeben wird, verworfen wird und der Code wie gewöhnlich weiterläuft und schließlich 2 zurückgibt.

Um dies zu beheben, fügen Sie in diesen return Aussagen:

else if (value > values[middle]) 
{ 
    low = middle; 
    return search(value, values, n, high, low); 
} 

else if (value < values[middle]) 
{ 
    high = middle; 
    return search(value, values, n, high, low); 
} 

Generell, wenn Sie, dass eine if Aussage Zustand vermuten feuert nicht, es ist langsam wert mit einem Debugger durch die Dinge zu treten. Dies würde wahrscheinlich dazu führen, dass Sie bemerken, dass Sie (1) die Funktion rekursiv korrekt aufrufen, aber (2) den zurückgegebenen Wert zurückgeben und verwerfen.

Möglicherweise gibt es andere Probleme mit dem Code hier, aber das ist sicherlich etwas, das Sie adressieren müssen.

Answer 2

Quothcb3k

, dass es funktionieren zu machen schien ... was könnten die anderen Probleme sein?

Hier ist der Code mit dem minimal (notwendig, aber nicht ausreichend) fix diagnostiziert durch templatetypedef und einem Test-Harnisch.

#include <stdio.h> 

static 
int search(int value, int values[], int n, int high, int low) 
{ 
    if (n <= 0) 
    { 
     return 1; 
    } 

    int middle = (high + low)/2; 

    ///condition #1 
    if (value == values[middle]) 
    { 
     return 0; 
    } 

    // conditions #2 and #3 (account for the maxes and mins of the array because the operation to find middle truncates) 
    else if (values[middle] == values[low] || values[middle] == values[high]) 
    { 
     return 0; 
    } 

    else if (value > values[middle]) 
    { 
     low = middle; 
     return search(value, values, n, high, low); 
    } 

    else if (value < values[middle]) 
    { 
     high = middle; 
     return search(value, values, n, high, low); 
    } 

    return 2; 
} 

int main(void) 
{ 
    int data[15]; 
    for (int i = 0; i < 15; i++) 
     data[i] = 2 * i + 1; 

    printf("Data:"); 
    for (int i = 0; i < 15; i++) 
     printf("%3d", data[i]); 
    putchar('\n'); 

    for (int i = -1; i < 2 * 15 + 3; i++) 
     printf("Search for %2d - result %d\n", i, search(i, data, 15, 14, 0)); 
    return 0; 
} 

Hier ist der Ausgang:

Data: 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 
Search for -1 - result 0 
Search for 0 - result 0 
Search for 1 - result 0 
Search for 2 - result 0 
Search for 3 - result 0 
Search for 4 - result 0 
Search for 5 - result 0 
Search for 6 - result 0 
Search for 7 - result 0 
Search for 8 - result 0 
Search for 9 - result 0 
Search for 10 - result 0 
Search for 11 - result 0 
Search for 12 - result 0 
Search for 13 - result 0 
Search for 14 - result 0 
Search for 15 - result 0 
Search for 16 - result 0 
Search for 17 - result 0 
Search for 18 - result 0 
Search for 19 - result 0 
Search for 20 - result 0 
Search for 21 - result 0 
Search for 22 - result 0 
Search for 23 - result 0 
Search for 24 - result 0 
Search for 25 - result 0 
Search for 26 - result 0 
Search for 27 - result 0 
Search for 28 - result 0 
Search for 29 - result 0 
Search for 30 - result 0 
Search for 31 - result 0 
Search for 32 - result 0 

Es 0 unabhängig davon zurückkehrt, ob der gesuchte Wert im Array vorhanden ist oder nicht. Dies ist ein falsches Verhalten.

Sie sollten eine Auszeit nehmen, um Programming Pearls von Jon Bentley zu studieren. Es deckt die Grundlagen des Testens von binären Suchen in einer Vielzahl von Formen ab - das gezeigte Test-Harness ist eine Variante dessen, was er beschreibt. Nehmen Sie sich auch die Zeit und lesen Sie Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken. Vielleicht sollten Sie beruhigt sein, dass viele andere Leute im Laufe der Zeit eine binäre Suche falsch gemacht haben. (IIRC, die ersten Versionen der binären Suche wurden in den 1950er Jahren veröffentlicht, aber erst in den frühen 1960er Jahren wurde eine korrekte Version veröffentlicht - und dann gibt es die Extra-Information von 2006 ebenfalls.)

Als ich hinzugefügt habe a printf() im Block nach else if (values[middle] == values[low] || values[middle] == values[high]), druckte es auf jeder Suche, die fehlgeschlagen sein sollte. Beachten Sie, dass die Schnittstelle es schwierig macht zu erkennen, was passiert - es wird nicht gemeldet, wo das Element gefunden wurde, sondern nur, ob es gefunden wurde. Sie können die Debugging- und Codeänderungen hinzufügen, die erforderlich sind, um mit den verbleibenden Problemen fertig zu werden. (Hinweis: Diese Bedingung ist wahrscheinlich kein Teil der Lösung. Wenn Sie sie jedoch entfernen, geht der Code in eine permanente Schleife über, weil Sie den Wert nicht eliminieren, von dem bekannt ist, dass er nicht in dem Bereich liegt, den Sie rekursiv überprüfen . zu arbeiten)

Dies scheint - beachten Sie, dass return 2; nie ausgeführt wird (weil die endgültige else if nie falsch ist

#include <stdio.h> 

static 
int search(int value, int values[], int n, int high, int low) 
{ 
    //if (n <= 0) 
    if (n <= 0 || high < low) 
    { 
     return 1; 
    } 

    int middle = (high + low)/2; 

    ///condition #1 
    if (value == values[middle]) 
    { 
     return 0; 
    } 

#if 0 
    // conditions #2 and #3 (account for the maxes and mins of the array because the operation to find middle truncates) 
    else if (values[middle] == values[low] || values[middle] == values[high]) 
    { 
     //printf(" (#2 || #3) "); 
     return 0; 
    } 
#endif 

    else if (value > values[middle]) 
    { 
     //low = middle; 
     low = middle + 1; 
     return search(value, values, n, high, low); 
    } 

    else if (value < values[middle]) 
    { 
     //high = middle; 
     high = middle - 1; 
     return search(value, values, n, high, low); 
    } 

    return 2; 
} 

int main(void) 
{ 
    int data[15]; 
    for (int i = 0; i < 15; i++) 
     data[i] = 2 * i + 1; 

    printf("Data:"); 
    for (int i = 0; i < 15; i++) 
     printf("%3d", data[i]); 
    putchar('\n'); 

    for (int i = -1; i < 2 * 15 + 3; i++) 
     printf("Search for %2d - result %d\n", i, search(i, data, 15, 14, 0)); 
    return 0; 
} 

Ausgang:.

Data: 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 
Search for -1 - result 1 
Search for 0 - result 1 
Search for 1 - result 0 
Search for 2 - result 1 
Search for 3 - result 0 
Search for 4 - result 1 
Search for 5 - result 0 
Search for 6 - result 1 
Search for 7 - result 0 
Search for 8 - result 1 
Search for 9 - result 0 
Search for 10 - result 1 
Search for 11 - result 0 
Search for 12 - result 1 
Search for 13 - result 0 
Search for 14 - result 1 
Search for 15 - result 0 
Search for 16 - result 1 
Search for 17 - result 0 
Search for 18 - result 1 
Search for 19 - result 0 
Search for 20 - result 1 
Search for 21 - result 0 
Search for 22 - result 1 
Search for 23 - result 0 
Search for 24 - result 1 
Search for 25 - result 0 
Search for 26 - result 1 
Search for 27 - result 0 
Search for 28 - result 1 
Search for 29 - result 0 
Search for 30 - result 1 
Search for 31 - result 1 
Search for 32 - result 1