Bug in recursive divide et impera binary search

Question

I wrote a divide and conquer binary search, it works in all cases except for when I search for the first or the last number, where instead of giving me 0 and v.size()-1 as the result it gives me 1 and v.size()-2.

For example if I input n=5 and the vector {1; 2; 3; 4; 5} and search for 1 it returns me "1" instead of "0".

#include <iostream>
#include <vector>

using namespace std;

int binarySearch(std::vector<int> v, int nr, int left, int right)
{
int mij = (left + right) / 2;

if (v[mij] < nr){
    binarySearch(v, nr, mij+1, right);
}
else if (v[mij] > nr){
    binarySearch(v, nr, left, mij-1);
}
else if (v[mij] == nr){
    return mij;
}
else return -1;
}

int main()
{
vector <int> v;

int n; cout << "n="; cin >>n;
for (int i = 0; i < n; i++){
    int x;
    cout << "v[" << i << "]=";
    cin >> x;
    v.push_back(x);
}

cout << binarySearch(v, 1, 0, v.size());

return 0;
}

Answer 1

Your code has undefined behavior because you do not return a value from your function in all cases. Your program might crash, do nothing, format your hard drive or give you the correct value - it's undefined what happens. In this case, your compiler knows exactly what the problem is and really wants to tell you, but you need to ask it: Turn on the warnings (e.g. -Wall in gcc or clang).

warning: control may reach end of non-void function [-Wreturn-type]

Currently, you do not return a value if you recurse, which is easily fixed:

int binarySearch(std::vector<int> v, int nr, int left, int right)
{
    int mij = (left + right) / 2;

    if (v[mij] < nr){
        return binarySearch(v, nr, mij+1, right);
//      ^^^^^^
    }
    else if (v[mij] > nr){
        return binarySearch(v, nr, left, mij-1);
//      ^^^^^^
    }
    else if (v[mij] == nr){
        return mij;
    }
    else return -1;
}