二进制搜索算法 C++

Question

我正在尝试编写一个函数，它接受一个整数数组并在数组的第一个和最后一个之间的部分搜索给定值。如果值在数组中，return那个位置。如果不是，我想 return -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 循环？这是我为实现二进制搜索功能而遵循的伪代码：

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

Answer 1

如果使用while循环就不需要递归了，只需要记住每次计算guess，并将guess设置到索引的中间，而不是它们的值：

int binarySearch (int *array, int first, int last, int value)
{

    int guess = 0;

    while (first != last || array[guess] == value) {
        guess = (first + last) / 2;

        if (array[guess] == value)
            return guess;
        else if (array[guess] < value)
            last = guess + 1;
        else if (array[guess] > value)
            first = guess - 1;
    }

    return -1;
}

我也建议

int first = 0, last = sizeof(array) / sizeof(array[0]) - 1;

而不是将它们作为参数传递。

Answer 2

我认为更改函数 returns 是有意义的。如果找到该项目，它应该 return 一个有效索引，而不是 returning guess，否则应该是 -1。

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

guess是下面的一个值。

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

guess是下面的索引。

    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);
   }
}

二进制搜索算法 C++

Binary Search algorithm c++

c++

function

binary-search