("vector subscript out of range") 用于二进制搜索问题

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 个问题：

在二分搜索函数中，您首先为参数分配新值，这将导致无限递归。只需删除此分配。

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

("vector subscript out of range") 用于二进制搜索问题

("vector subscript out of range") for Binary search problem

c++

algorithm

vector

binary-search