Блог

Главная - Вопросы по программированию - Я не понимаю, почему мой код для двоичного поиска отображает ошибку сегментации

Я не понимаю, почему мой код для двоичного поиска отображает ошибку сегментации

#c

#c

Вопрос:

Я протестировал код для вектора a = {1,5,8,12,13} и x = 23, он отправил мне ошибку сегментации, и я не понимаю, почему :

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

using std::vector;

int binary_search(const vector<int> amp;a, int x) {
    int left = 0, right = (int)a.size(); 
    if(left>right) return -1;
    right = floor((double)(left   right)/2);
    if(a[right] == x){
        return right;
    }
    else if(a[right]>x){
        vector<int> w(a.begin(), a.begin()   right);
        return binary_search(w,x);
    }
    else{
        vector<int> w(a.begin()   right, a.end());
        return binary_search(w,x);
    }
}

Он должен войти в бесконечный цикл, когда вектор w, созданный программой, имеет размер 1, нет?

Комментарии:

1. Посмотрите на if(a[right] == x) . Вы пытаетесь получить a[a.size()] когда вектор пуст или состоит из одного элемента. Разве вы не видите здесь проблему?

2. if(left>right) return -1; является избыточным. 0 > что-то неподписанное никогда не происходит.

3. Вместо того, чтобы копировать вектор в кучу, почему бы просто не передать его ref с start и end индексом. Еще лучше, используйте std::span

4. en.cppreference.com/w/cpp/algorithm/binary_search

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

Ответ №1:

У нас могут быть индексы start и end , которые могут указывать на подмассив, в котором вы хотите выполнить двоичный поиск, таким образом, нам не нужно явно создавать подмассив.

 int binary_search(vector<int> amp;a, int start, int end, int x) {
    if(start > end) 
       return -1;
    int mid = floor((double)(start   end)/2);
    if(a[mid] == x){
        return mid;
    }
    else if(a[mid] > x){
        return binary_search(a, 0, mid - 1, x);
    }
    else{
        return binary_search(a, mid   1, end, x);
    }
}