Не работает бинарный поиск, а точнее return c++

Question

Писал алгоритм двоичного поиска, почем-то неправильно работает return. Если сделать void функцию с выводом ответа, то работает...

/* Binary search */

#include <iostream>
#include <vector>

using namespace std;

int binarySearch(int find, vector<int> numbers, int left, int right) {
    int mid = left + right + 1 >> 1;
    if (find == numbers[mid]) return mid;
    find > numbers[mid] ? binarySearch(find, numbers, mid + 1, right) : binarySearch(find, numbers, left, mid - 1);
}

int main() {
    int n, find;
    cin >> n;
    vector<int> numbers(n);
    for (int i = 0; i < n; ++i) {
        cin >> numbers[i];
    }
    cin >> find;
    cout << binarySearch(find, numbers, 0, n - 1);
}

Answer 1

Во первых, вы надеетесь, что введете элементы вектора в отсортированном порядке. В таком случаи зачем их вводить вообще, если можно сразу инициализировать вектор этими данными? Но, тв любом случаи, не мешает проверить не отсортирован ли вектор? Для этого есть стандартный алгоритм.

Во вторых, функцию бинарного поиска нужно написать правильно. Вы вызываете рекурсивно функцию, но не пользуйтесь возвращаемым ей значением и не возвращаете ничего. А если нет такого элемента? Что тогда? А если mid <= 0 что тогда? В любом случаи, если функция должна возвращать что то, то она должна возвращать при любых обстоятельствах. И по какой логике у вас int mid = left + right + 1 >> 1;? Где скобки в выражении, выполняющая несколько операций? Вы уверены в приоритетах?... И почему еще единицу прибавляете к среднему элементу(это ни к чему)? И зачем вы копируете вектор?... И операцию деления нужно выполнять, если условие выполняется. В итоге, если написать так:

int
binarySearch(int find, const vector<int>& numbers, int left, int right) {
    int mid = (right - left);   
    
    if (mid > 0 ) {
        mid >>= 1;
        if(find != numbers[mid])
            //обратите внимание на присваивание
            mid = find > numbers[mid] 
                  ? binarySearch(find, numbers, mid + 1, right) 
                  : binarySearch(find, numbers, left, mid);        
    }        
    return mid;
}

где rightиндекс последнего элемента, то функция вернет нужный результат. А еще лучше передать в функцию тип unsigned в качестве индексов, и с модификаторами constи возвращать из функции такой же тип(unsigned mid). Тогда будет понятно, что не нужно передать отрицательное число, и ваша функция не изменяет их значения.

БЛОГ НА HUSL

Не работает бинарный поиск, а точнее return c++

Ответы (1 шт):