PSet 3 - CS50 - 二進制搜索實用

這是來自edX.org CS50課程的PSET 3。PSet 3 - CS50 - 二進制搜索實用

我一直在努力解決這個問題很長一段時間;特別是，我無法使binarySearch函數正常工作。我不斷收到分段錯誤，我無法弄清楚如何處理它。我花了很多時間思考這個問題，我只是沒有看到它。

這是我的代碼。有人可以從概念上指出我要去哪兒嗎？謝謝。

#include <stdio.h> 
#include <cs50.h> 

bool binarySearch(int value, int values[], int min, int max) 
{ 
    bool answer = false; 

    if (max < min) 
    { 
     answer = false; 
    } 

    else if (values[max] == value) 
    { 
     answer = true; 
    } 

    else if (values[min] == value) 
    { 
     answer = true; 
    } 

    else 
    { 
     int midPoint = (max + min)/2; 

     if (values[midPoint] == value) 
     { 
      answer = true; 
     } 

     else if (values[midPoint] > value) 
     { 
      answer = binarySearch(value, values, min, midPoint); 
     } 

     else 
     { 
      answer = binarySearch(value, values, midPoint, max); 
     } 
    } 

    return answer; 
} 

int main (int argc, char *argv[]) 
{ 
    int value = 34; 

    int values[] = {11,22,33,44,55,66,77,88,99,1010}; 

    int max = sizeof(values)/sizeof(int); 

    if (binarySearch(value, values, 0, max - 1)) 
    { 
     printf("Found needle!\n"); 
    } 

    else 
    { 
     printf("Did not find needle\n"); 
    } 
}

當我搜索的值不在數組中時，我總是收到分段錯誤。

來源

2014-04-23 user3237895

這已經晚了，我的大腦正在關閉。在審查你的代碼時，可能是行'int max = sizeof（values）/ sizeof（int）;'你可能希望'printf（「max [％d] \ n」，max）;'並確認它打印出你期望的（即：10？）。 –

爲什麼不用'while'做簡單的迭代？它比遞歸更簡單，更快速，更安全... – CiaPan

@Mahonri - 我之前測試過它，它會出現最大的正確大小。 – user3237895

我想你應該你的代碼更改爲：

else 
    { 
     int midPoint = (max + min)/2; 

     if (values[midPoint] == value) 
     { 
      answer = true; 
     } 

     else if (values[midPoint] > value) 
     { 
      answer = binarySearch(value, values, min, midPoint-1); // not midPoint 
     } 

     else 
     { 
      answer = binarySearch(value, values, midPoint+1, max); //not midPoint 
     } 
    }

來源

2014-04-23 06:10:50 BlackMamba

這工作！你不會相信我在這上面花了多長時間。儘管我已經學到了很多東西。然而，你能向我解釋爲什麼有必要添加midPoint-1和midPoint + 1.我試圖在紙上找出這些，這對我沒有意義。 – user3237895

@ user3237895嘗試使用一張紙和一支鉛筆按照您的程序進行操作，同時在唯一值爲「3」的單項數組中搜索「7」。 – CiaPan

的問題是在這裏

if (max < min)

最終max將等於min，但沒有在代碼中的力量max變得小於min。因此，如果指定的值不在數組中，該函數將永久遞歸。

來源

2014-04-23 06:01:28 user3386109

PSet 3 - CS50 - 二進制搜索實用

回答

相關問題