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++二进制搜索功能

回答

相关问题