Binary search, or rather return c++, does not work

Question

Binary search, or rather return c++, does not work

I wrote a binary search algorithm, why does return work incorrectly? If you make a void function with the output of the response, it works...

/* 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);
}

0

c++алгоритм функции return поиск

Author: Аркадий, 2020-07-11

Source

1 answers

score 2 · Accepted Answer

First, you hope to enter the elements of the vector in a sorted order. In this case, why enter them at all, if you can immediately initialize the vector with this data? But, in any case, it does not hurt to check whether the vector is sorted? There is a standard algorithm for this.

Secondly, the binary search function must be written correctly. You call the function recursively, but do not use the value returned to it, and do not return anything. And if there is no such element? What then? And if mid <= 0 what then? In any case, if a function should return something, then it should return under any circumstances. And by what logic do you have int mid = left + right + 1 >> 1;? Where are the parentheses in an expression that performs multiple operations? Are you sure about the priorities?... And why else do you add one to the average element(this is not necessary)? And why are you copying the vector?... And the division operation must be performed if the condition is met. As a result, if you write like this:

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;
}

Where rightis the index of the last the function returns the desired result. And it is even better to pass the type unsigned to the function as indexes, and with the modifiers constand return the same type from the function (unsigned mid). Then it will be clear that you do not need to pass a negative number, and your function does not change their values.