二元递归函数计数不正确

Question

所以这段代码的想法是，我有一个使用递归的二分搜索函数，我所添加的功能是它计算已经发生的递归数量，它还计算它进行的比较数量并输出它。然而，在这个项目中，我遇到了代码输出错误数量的递归和比较的问题。 这是代码：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Global variables to count calls and comparisons
int recursions = 0;
int comparisons = 0;

// Read integers from input and store them in a vector.
// Return the vector.
vector<int> ReadIntegers() {
   int size;
   cin >> size;
   vector<int> integers(size);
   for (int i = 0; i < size; ++i) {               // Read the numbers
      cin >> integers.at(i);
   }
   sort(integers.begin(), integers.end());
   return integers;
}

   int BinarySearch(int target, vector<int> integers, int lower, int upper) {
    if(lower<=upper){
        int mid = lower +(upper - lower) / 2;

        comparisons++;

        if(integers.at(mid) == target){
            return mid;
        }
        else if (integers.at(mid) < target){
            recursions++;
            return BinarySearch(target, integers, mid +1, upper);
        }
        else if (integers.at(mid) > target){
            recursions++;
            return BinarySearch(target, integers, lower, mid -1);
        }
    }

    return -1;

}

int main() {
   int target;
   int index;

   vector<int> integers = ReadIntegers();

   cin >> target;

   index = BinarySearch(target, integers, 0, integers.size() - 1);
   printf("index: %d, recursions: %d, comparisons: %d\n",
          index, recursions, comparisons);

   return 0;
}

所以我输入的是：

9
1 2 3 4 5 6 7 8 9
2

输出应该是：

index: 1, recursions: 2, comparisons: 3

疯狂古怪的事情是我不断得到错误数量的递归和比较，因为我的程序输出如下：

index: 1, recursions: 1, comparisons: 2

感觉我总是一矮一高。该函数毫无问题地找到索引。

也许这对我来说是一个逻辑错误，但我确实相信我做的一切都是正确的。我只是缺少一些东西。

如果有人可以帮助我纠正我做错的事情，我将不胜感激！非常感谢您。

Answer 1

我认为你的代码实际上是正确的。尝试在

BinarySearch()

中放入 print 语句，以便在每次计算时打印

mid

的值。我想你会发现检查的第一个索引是 4，然后递归，下一个索引是 1，这就是你的目标。