CODEWITHSUNDEEP
c++recursionbinary-search
Gourav kr Singh
Gourav kr Singh

Reputation: 97

Recursive binary search errors in c++

I'm trying to write a recursive binary search function using below approach. I'm basically using divide and conquer strategy and everything looks good to me in code, but unable to figure out where my code and approach goes wrong.

#include<iostream>
using namespace std;
bool b_search(int *arr, int n, int start, int end){
    if(start==end){
        if(arr[start]==n){
            return true;
        }
        else{
            return false;
        }
    }
    else{
        int mid=start+(end-start)/2;
        if(arr[mid]==n){
            return true;
        }
        else if(arr[mid]>n){
            return b_search(arr,n,mid+1,end);
        }
        else{
            return b_search(arr,n,start,mid-1);
        }
    }

}
int main(){
    int arr[8]={3,5,8,11,13,15,16,25};
    cout<<b_search(arr,16,0,7);
}

I'm getting output as zero but it should be 1.

Upvotes: 1

Views: 97

Answers (3)

Ted Lyngmo
Ted Lyngmo

Reputation: 117298

When arr[mid]>n you then search for the number in the part with higher number which is guaranteed to miss. You need to search in the part with lower numbers.

Example:

bool b_search(int *arr, int n, int start, int end) {
    if (start == end) return arr[start] == n;

    int mid = start + (end - start) / 2;

    if (arr[mid] < n) { // arr[mid] is lower than n, search in the high part
        return b_search(arr, n, mid + 1, end);
    } else if (arr[mid] > n) { // arr[mid] is greater than n, search lower part
        return b_search(arr, n, start, mid - 1);
    }

    return true;
}

Upvotes: 1

RoQuOTriX
RoQuOTriX

Reputation: 3001

You are searching in the wrong direction. If arr[mid] > n then you should be searching from start to mid -1 and the other way around. The reason is that your searched value n is then in the other half of your searched array

#include<iostream>
using namespace std;
bool b_search(int *arr, int n, int start, int end)
{
    if(start==end)
    {
        if(arr[start]==n)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    else
    {
        int mid=start+(end-start)/2;
        if(arr[mid]==n)
        {
            return true;
        }
        else if(arr[mid]<n) // turn around the comparison
        {
            return b_search(arr,n,mid+1,end);
        }
        else
        {
            return b_search(arr,n,start,mid-1);
        }
    }

}
int main()
{
    int arr[8]={3,5,8,11,13,15,16,25};
    cout<<b_search(arr,16,0,7);
}

Upvotes: 1

463035818_is_not_an_ai
463035818_is_not_an_ai

Reputation: 122476

Your next interval is wrong.

    else if(arr[mid]>n){
        return b_search(arr,n,mid+1,end);

When the middle element is too large then you continue with the larger portion of the array. You should continue with the smaller portion of the array instead:

    else if(arr[mid]<n){
        return b_search(arr,n,mid+1,end);
    }
    else{
        return b_search(arr,n,start,mid-1);
    }

Upvotes: 1

Related Questions