c++ - 二进制搜索算法 C++

Question

我正在尝试编写一个函数，它接受一个整数数组并在数组的第一个和最后一个之间的部分搜索给定值。如果该值在数组中，则返回该位置。如果不是，我想返回-1。

这是我的函数的代码。

    int binarySearch(int *array, int min, int max, int value) {
    int guess = 0;
    bool found = false;
    while (!found) {
        guess = ((array[min] + array[max]) / 2);
        if (array[guess] == value) {
            found = true;
            return guess;
        }
        else if (array[guess] < value) {
            min = guess + 1;
        }
        else if (array[guess] > value) {
            max = guess - 1;
        }
    }
    return -1;
}

当您要搜索的值不在数组中时，我不确定如何跳出 while 循环？这是我为实现二进制搜索功能而遵循的伪代码:

1. 让 min = 0 和 max = n-1(数组大小 -1 )。将猜测计算为最大值和 min，向下舍入(因此它是一个整数)。
2. 如果数组[猜测]等于 目标，然后停止。你找到了!返回猜测。
3. 如果猜测太 low，即array[guess] < target，则设min = guess + 1。
4. 否则，猜测太高了。设置 max = guess - 1。
5. 回到第 2 步。

Answer 1

我认为更改函数返回的内容是有意义的。与其返回 guess，不如在找到项目时返回有效索引，否则返回 -1。

此外，您正在使用 guess 作为值和索引。这肯定会引起问题。

猜是下面的一个值。

    guess = ((array[min] + array[max]) / 2);

猜想是下面的一个索引。

    else if (array[guess] < value) {

这是我的建议:

// Return the index if found, -1 otherwise.
int binarySearch(int *array, int first, int last, int value)
{
   // Terminating condition 1.
   // If first crosses last, the item was not found.
   // Return -1.
   if ( first > last )
   {
      return -1;
   }

   int mid = (first + last)*0.5;

   // Terminating condition 2.
   // The item was found. Return the index.
   if ( array[mid] == value )
   {
      return mid;
   }

   // Recurse
   if (array[mid] < value)
   {
      return binarySearch(array, mid+1, last, value);
   }
   else
   {
      return binarySearch(array, first, mid-1, value);
   }
}