Recursive binary search errors in c++

Question

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.

Ted Lyngmo · Accepted Answer · 2022-08-02 07:43:34Z

1

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

answered Aug 2, 2022 at 7:43

Ted Lyngmo

124k7 gold badges93 silver badges155 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

463035818_is_not_an_ai · Accepted Answer · 2022-08-02 07:37:21Z

1

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

answered Aug 2, 2022 at 7:37

463035818_is_not_an_ai

128k11 gold badges116 silver badges240 bronze badges

Comments

RoQuOTriX · Accepted Answer · 2022-08-02 07:37:50Z

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

Collectives™ on Stack Overflow

Recursive binary search errors in c++

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related