(«векторный индекс вне диапазона») для задачи двоичного поиска - PullRequest
Новая
       15

(«векторный индекс вне диапазона») для задачи двоичного поиска

0 голосов
/ 02 мая 2020

Я пытаюсь реализовать функцию двоичного поиска в C ++, в этой функции я отсортировал вектор целых чисел, затем я ввожу вектор целых чисел, чтобы проверить индекс искомого значения. Если значение не найдено, -1 следует быть возвращенным

Проблема в том, что я получаю сообщение _DEBUG_ERROR («векторный индекс вне диапазона»); во время отладки.

Вот код 

 #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) << ' ';
    }
}

1 Ответ

1 голос
/ 02 мая 2020

С этим кодом есть 2 проблемы:

В функции двоичного поиска вы начинаете с присвоения вашим параметрам новых значений, что приведет к бесконечной рекурсии. Просто удалите это назначение.

Ваш средний назначен так: int mid = (left + ((left - right) / 2));, но должен быть таким: int mid = (left + ((right - left) / 2)); (ваш текущий средний всегда меньше или равен левому, и ваша ошибка появляется здесь, так как вы пытаетесь использовать отрицательный индекс)

...