Getting segmentation fault (core dump) for binary search(recursive) to find a number in an array-CodePudding

This is a problem to find the target number in an array using the binary search recursive method. Getting segmentation fault. Have tried a lot but cannot find what is causing it. need some help to avoid such mistakes. which part is wrong in my code?? I have pasted the complete code.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std ;


int recursivebinarysearch(vector <int>& arr ,int target , int ans ){
    int high = arr.size() - 1 ;
    int low = 0 ;
    int mid = (high   low) / 2 ;
    for(int i = 0 ; i < arr.size() ; i  ){
        
        mid = (low high)/2 ;
        if(low > high){
            mid = -1;
            return mid;
        }
        if(target > arr[mid]){
            low = mid  1 ;
            recursivebinarysearch(arr ,  target , ans );
        }
        else if(target < arr[mid]){
            high = mid -1;
            recursivebinarysearch(arr , target , ans );
        }
        else{
            mid = ans ;
            return ans ;
        }
    }
}
int main(){
    int n,   target , ans = 0;
    
    cin >> n  ;
    
    vector<int> arr ;
    int j = 0;
    for(int j = 0 ; j < n ; j  ){
        cin >> arr[j];
    }
    cin >> target ;
    sort(arr.begin() , arr.end());
    ans = recursivebinarysearch(arr,  target , ans);

    cout<<ans<<endl;

    return 0;
}

CodePudding user response：

high, low, mid are local to your function. So, each time you call recursivebinarysearch with the same vector arr, you get the same values. So, you infinitely recurse. The segmentation fault happens when the stack overflows.

If you want to keep this approach, you need to pass high and mid to the function and have it search this range only.

Alternatively, you can have a single while and adjust local values high, low as you go. This would be better, but some professors out there want to see explicit recursion.

Also, thanks to the comments, cin >> arr[j]; doesn't work. Either:

int value;
cin >> value;
arr.push_back(value);

arr.resize(j 1);
cin >> arr[j];

CodePudding user response：

First of all I do not understand why are you trying to implement binary search using recursion, when the standard implementation below is O(logN).

And as ikegami and Jeffry mentioned, you are recursively iterating without any change in arguments, so you eventually exhaust the stack, and cause segmentation fault.

#include <iostream>
#include <vector>

#define NOT_FOUND -1

int not_a_recursivebinarysearch(const std::vector<int> &v, const int x)
{
    std::vector<int>::size_type low = 0;
    std::vector<int>::size_type high = v.size() - 1;
    while(low <= high)
    {
        std::vector<int>::size_type mid = (low   high) / 2;
        if(v[mid] < x)
            low = mid   1;
        else if(v[mid] > x)
            high = mid - 1;
        else
            return mid;
    }
    return NOT_FOUND;
}

And as Avi Berger mentioned in comments, your logic to populate the vector is not correct either. C vectors use standard C type arrays under the hood, but they claim more capacity dynamically. Ofcourse, this can only happen when you use the right interface which is vector.push_back.

int main(){
    int n, target, ans = 0;
    int temp;
    
    cin >> n;
    
    vector<int> arr;

    // int j = 0;
    // This is not needed
    // The following loop already init-declares `j`

    for(int j = 0; j < n;   j){
        cin >> temp;
        arr.push_back(temp);
    }
    cin >> target;
    sort(arr.begin() , arr.end());
    ans = not_a_recursivebinarysearch(arr, target);

    cout << ans << endl;

    return 0;
}

A small improvement would be to check for -1 returned from recursivebinarysearch, and show a more meaningful result to user.

ans = not_a_recursivebinarysearch(arr, target)
if(ans == -1) cout << "NOT FOUND" << endl;
else cout << "FOUND at index: " << ans << endl;