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

Question

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

例如，如果我输入 n=5 和向量 {1; 2; 3; 4; 5} 并搜索 1 它 returns 我是“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

您的二进制搜索工作正常，但您确定您已正确地将输入传递给程序吗？输入应该是这样的 -

5
1 2 3 4 5

输出

你可以在这里验证link to code

Answer 2

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

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

目前，如果你递归，你不会return一个值，这很容易修复：

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

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

Bug in recursive divide et impera binary search

c++

recursion

binary-search

divide-and-conquer