C++二進制搜索功能

-2

我想創建一個二進制搜索功能。我用來測試的陣列是： {1,4,5,6,9,14,21,28,31,35,42,46,50,53,57,62,63,65,74,89 }C++二進制搜索功能

現在我想我已經涵蓋了所有的邊界問題，但搜索1和42回來，因爲沒有找到我無法解釋的。

注意：如果索引= -1，這意味着該searchKey尚未陣列

42中發現應在第一遍被返回作爲索引。
1應作爲第四通的索引返回。

都返回作爲索引= -1

int BinSearch(int data[], int numElements, int searchKey) 
{ 
    bool found = false; 
    int index; 
    int searchStart = 0; 
    int searchEnd = numElements - 1; 

    while (!found) 
    { 
     index = (searchEnd + searchStart)/2; 
     // If searchEnd is next to searchStart then check both to see if either is 
     // searchKey 
     if ((searchEnd - 1) == searchStart) 
     { 
      found = true; 
      if (searchKey == data[searchStart]) { 
       index = searchStart; 
      } 
      else if (searchKey == data[searchEnd]) { 
       index = searchEnd; 
      } 
      else { 
       index = -1; 
      } 
     } 
     // If index is less than searchStart or greater than searchEnd then searchKey 
     // isn't in the array 
     else if (index <= searchStart || index >= searchEnd) { 
      found = true; 
      index = -1; 
     } 
     else if (searchKey > data[index]) { 
      searchStart = index + 1; 
     } 
     else if (searchKey < data[index]) { 
      searchEnd = index - 1; 
     } 
     else if (searchKey == data[index]) { 
      found = true; 
     } 
    } 
    return index; 
}

來源

2014-09-18 Ben Mukasa

我懷疑使用['std :: lower_bound']（http://en.cppreference.com/w/cpp/algorithm/lower_bound）將被認爲是作弊。 – WhozCraig 2014-09-18 18:11:50

嗯... 42有索引10.所以它不會在第一遍中找到它。 – RockOnRockOut 2014-09-18 18:14:33

19/2 = 9.5，因爲你將它填充到整數中，所以它被截斷爲9。它在第一遍中找不到，因爲它在索引10處。 – SnowInferno 2014-09-18 18:18:47

更改此：

if ((searchEnd - 1) == searchStart)

這樣：

if ((searchEnd - 1) <= searchStart)

當尋找1，在第三通searchEnd將在3和searchStart將是0，因此索引爲1 。由於你的值在位置0，所以它會在第一遍中將searchEnd修改爲0。

來源

2014-09-18 18:18:24 RockOnRockOut

或者簡單地if（（searchEnd - 1）<= searchStart） – Slava 2014-09-18 18:19:55

好點 - 我改變了它。 – RockOnRockOut 2014-09-18 18:42:47

非常感謝。它解決了我的問題。我認爲這個整數是四捨五入而不是四捨五入，即4.5會變成5而不是4。 – 2014-09-18 18:47:09

42將不會在第一遍中找到，因爲它是在指數10，但你必須searchEnd = 19和searchStart = 0，所以第一個索引是9.
我認爲真正的問題在於，如果索引== searchStart或索引== searchEnd，而沒有首先檢查searchKey == data [index]，那麼您將會紓困。

來源

2014-09-18 18:14:59 dohashi

C++二進制搜索功能

回答

相關問題