c++ - 递归 divide et impera 二进制搜索中的错误

Question

我写了一个分而治之的二进制搜索，它在所有情况下都有效，除了当我搜索第一个或最后一个数字时，而不是给我 0 和 v.size()-1 作为结果它给我1 和 v.size()-2。

例如，如果我输入 n=5 和 vector {1; 2; 3; 4; 5} 并搜索 1，它返回“1”而不是“0”。

#include <iostream>
#include <vector>

using namespace std;

int binarySearch(std::vector<int> v, int nr, int left, int right)
{
int mij = (left + right) / 2;

if (v[mij] < nr){
    binarySearch(v, nr, mij+1, right);
}
else if (v[mij] > nr){
    binarySearch(v, nr, left, mij-1);
}
else if (v[mij] == nr){
    return mij;
}
else return -1;
}

int main()
{
vector <int> v;

int n; cout << "n="; cin >>n;
for (int i = 0; i < n; i++){
    int x;
    cout << "v[" << i << "]=";
    cin >> x;
    v.push_back(x);
}

cout << binarySearch(v, 1, 0, v.size());

return 0;
}

Answer 1

您的代码具有未定义的行为，因为您并非在所有情况下都从函数返回值。您的程序可能会崩溃，什么都不做，格式化您的硬盘驱动器或给您正确的值 - 不确定会发生什么。在这种情况下，您的编译器确切地知道问题是什么并且真的想告诉您，但您需要询问它:打开警告(例如 gcc 或 clang 中的 -Wall)。

warning: control may reach end of non-void function [-Wreturn-type]

目前，如果你递归，你不会返回一个值，这很容易修复:

int binarySearch(std::vector<int> v, int nr, int left, int right)
{
    int mij = (left + right) / 2;

    if (v[mij] < nr){
        return binarySearch(v, nr, mij+1, right);
//      ^^^^^^
    }
    else if (v[mij] > nr){
        return binarySearch(v, nr, left, mij-1);
//      ^^^^^^
    }
    else if (v[mij] == nr){
        return mij;
    }
    else return -1;
}