("向量下标超出范围")的二进制搜索问题。

Question

我想用C++实现二进制搜索函数，在这个函数中，我对整数向量进行了排序，然后我输入整数向量来检查我要搜索的值的索引，如果没有找到，则返回-1。

问题是我在调试时收到了消息_DEBUG_ERROR("vector subscript out of range");。

以下是代码

 #include <iostream>
#include <cassert>
#include <vector>

using std::vector;

int binary_search(const vector<int> &a, int x, int left, int right) {
    left = 0;
    right = (int)a.size();
    if (left > right) return -1;
    int mid = (left + ((left - right) / 2));
    if (a[mid] == x)
    {
        return mid;
    }
    else if (x > mid)
    {
        return binary_search(a, x, mid + 1, right);
    }
    else if (x < mid)
        return binary_search(a, x, left, mid - 1);
}

int linear_search(const vector<int> &a, int x) {
    for (size_t i = 0; i < a.size(); ++i) {
        if (a[i] == x) return i;
    }
    return -1;
}

int main() {
    int n;
    std::cin >> n;
    vector<int> a(n);
    for (size_t i = 0; i < a.size(); i++) {
        std::cin >> a[i];
    }
    int m;
    std::cin >> m;
    vector<int> b(m);
    int left =0;
    int right= (int)a.size() - 1 ;
    for (int i = 0; i < m; ++i) {
        std::cin >> b[i];
    }
    for (int i = 0; i < m-1; ++i) {

        std::cout << binary_search(a, b[i], left, right) << ' ';
    }
}

Answer 1

这个代码有2个问题。

在二进制搜索函数中，你开始给你的参数分配新的值， 这会导致无限的递归。把这个赋值去掉就可以了。

你的中值是这样分配的 int mid = (left + ((left - right) / 2)); 但应该是这样。int mid = (left + ((right - left) / 2)); (你的当前中值总是小于或等于左，而你的错误就出现在这里，因为你试图使用负指数)