I Wrote a program for binary search using cpp. Its working fine except if the Searched Element is not found in the Vector, its returning Garbage value while it should be returning 0.

Here's the code -

#include<iostream>
#include<vector>
using namespace std;
int BinarySearch(vector<int> v,int x,int y,int t){
    if(x>y){
        return 0;
    }
    else{
        int m=x (y-x)/2;
        if(v[m]==t)
        return m;
        else if(v[m]>t){
            BinarySearch(v,x,m-1,t);
        }
        else
        BinarySearch(v,m 1,y,t);
    }
}
main(){
    int n,m=0,no;
    vector <int> v;
    cout<<"Enter the No of Elements u wanna store in the Array : ";
    cin>>n;
    while(n--){
        cout<<"Enter Element "<<  m<<" : ";
        int t;
        cin>>t;
        v.push_back(t);
    }
    cout<<"Enter the no u wanna search for : ";
    cin>>no;
    int Start=0,End=v.size()-1;
    int B=BinarySearch(v,Start,End,no);
    if(B==0){
        cout<<"Element not Found\n";
    }
    else{
        cout<<"The Element is : Element "<<B 1;
    }
}

CodePudding user response：

There is a logical error in the section

if(B==0){
        cout<<"Element not Found\n";
    }

as if an element is found at index 0 then its going to print element not found.

You can use this as a solution:

#include <iostream>
#include <vector>
int BinarySearch(std::vector<int> vec, int start, int end, int num)
{
    if (start >= 1)
    {

        int mid = 1   (end - start) / 2;
        if (vec[mid] == num)
            return mid;
        if (vec[mid] > num)
        {
            return BinarySearch(vec, start, mid - 1, num);
        }

        return BinarySearch(vec, mid   1, end, num);
    }
    return -1;
}

this line:

int m=x (y-x)/2;

is flawed as x is going to be 0 except in the case of the recursive call BinarySearch(v,m 1,y,t); as well as the fact that you're just calling it and not returning the value of the function call

Essentially, the answer to your question is that it is returning a garbage value instead of 0 because the condition of the outer if statement in your BinarySearch function is not being met and having no other return statement in your function being the reason.

P.s. having meaningful parameter/variable names is important practice especially when having others read your code

CodePudding user response：

1. You are just calling BinarySearch function again without returning its value
2. Returning 0 is wrong because you will not know whether it exists at 0 or not found
3. You should sort the vector: #include<algorithm> then std::sort(v.begin(), v.end());
4. Write int main() or void main() not main() because the third does not work on all compilers
5. Pass std::vector by const reference const std::vector& v in the function
6. Better not using namespace std
7. I think m = (x y)/2 looks more elegant