修改的二進制搜索數組

我目前的邏輯不正確。我想要一個可以找到整數「wantToFind」的二分法搜索，如果它不在數組中，將從wantToFind中減1，直到找到它。

我已經從一個較大的程序中減去了這個值，這保證了數組中的第一項將是最低的wantToFind（我們希望找到的值）。

然而，儘管下面的二進制搜索公約的程序還是會被尋求更高的數字，如88

float list[15] = {60,62,64,65,67,69,71,72,74,76,77,79,81,83,84}; 

//binary search 
int wantToFind = 88; //other tests are 65, 61, 55 
bool itemFound = false; 

int current = 0; 
int low = 0; 
int high = 14; 

current = (low+high)/2; 
//int previousCurrent = -1; 

do { 
    do { 
     //if 61 < 72 
     if (wantToFind < list[current]) 
     { 
      //smaller 
      //previousCurrent = current; 
      high = current - 1; 
      current = (low+high/2); 
     } 
     else if (wantToFind > list[current]) 
     { 
      //bigger 
      //previousCurrent = current; 
      low = current + 1; 
      current = (low+high/2); 
     } 
     else{ 
      if(wantToFind == list[current]) 
      { 
       itemFound = true; 
      } 
     } 

    } while (low >= high); 

    if (itemFound == false) 
    { 
     wantToFind--; 
    } 
} while (itemFound == false); 

printf("\n%d", wantToFind); //which will be a number within the list? 
    return 0;

}

來源

2016-11-23 Corey Ford

只是爲了確保我正確理解你 - 你已經拿到了你在某處找到的這段代碼，並且你要求我們向你解釋它是如何工作的？你自己做過什麼研究嗎？通過代碼讀取，用各種輸入調試它等？如果是，請分享。例如，你能夠了解哪些部分以及哪些部分無法理解？ –

@barakmanos不完全。我想要一個可以找到整數「wantToFind」的二分法搜索，如果它不在數組中，將從wantToFind中減1，直到找到它。此代碼目前無法使用。對缺乏清晰度的道歉 –

因此，您的代碼無法正常工作...和？您希望我們爲您進行調試並解釋原因？ –

我無法想像爲什麼你要while (low >= high)。這將導致循環首次終止。我很確定你想要while (low <= high)。

此外，在沒有找到項目，有三種可能性：

wantToFind比列表中的最小項小。
wantToFind大於列表中最大的項目。
wantTofind將位於列表中的某處。

在情況2和3，current值當內循環退出會比一個包含第一項比wantToFind越小指數一個。

在情況下大於1，將current等於0

的一點是，沒有必要爲外環。當二分查找失敗時，current的值會告訴您插入點。

另外，您可能希望在找到該物品時提前退出。

最後，幫你一個忙，把do...while變成while循環。那就是：

while (!itemFound && low <= high)

你會發現一個更容易推理。

來源

2016-11-23 14:19:44

你的退出條件應該是low >= high時卡住。然後你會發現第一個值，或者小於或者大於目標值（或者當然是你正在搜索的值）。那麼你不再需要這個if語句：if (current < 0 || current > 14)但你必須在循環之後檢查/調整結果。

來源

2016-11-23 13:44:06

因此，如果我將'itemFound == false'改爲'low> = high'，並且在測試'if（itemFound == false）''then wantToFind - ''然後在'itemFound == false'的同時把所有這些包裝在一起呢？（將更新上面的代碼） –

修改的二進制搜索數組

回答

相關問題