segmentation fault in recursive binary searching

Question

I want to binary search more than once using the same function but it's showing segmentation fault. For one input its giving correct answer but when I am giving multiple input for binary search(i.e, q>1 acc. to my code) then its showing segmentation fault.

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int binarySearch(int x[],int l, int r, long int m ){
    if(r>=1){
        int mid=(r-1)/2+l;
        if (x[mid]==m) return mid;
        if (x[mid]>m) return binarySearch(x,l,mid-1,m);
        if (x[mid]<m) return binarySearch(x,mid+1,r,m);
    }
    return 0;
}
int main(){
    int n,q;
    cin>>n;
    int x[n];
    for(int i=0;i<n;i++){cin>>x[i];}
    int t = sizeof(x) / sizeof(x[0]);
    sort(x,x+t);
    cin>>q;
    while (q--){
        long int m;
        cin>>m;
        cout<<binarySearch(x,0,t-1,m)<<endl;
        
    }
    
    
    
    return 0;
}

Obligatory [Why is “using namespace std;” considered bad practice?](https://stackoverflow.com/q/1452721/3282436) and [Why should I not #include ?](https://stackoverflow.com/q/31816095/3282436) — 0x5453, May 21 '21 at 19:12
use `std::lower_bound` instead of implementing binary search yourself. — Aykhan Hagverdili, May 21 '21 at 19:13
And one of the reasons for the above is a sufficiently large `n`, and that can be a few thousand on some systems, will blow the out of the stack. — user4581301, May 21 '21 at 19:16
`int t = sizeof(x) / sizeof(x[0]);` This is a very strange thing to do, given that you have used `n` right in the previous line. — n. m. could be an AI, May 21 '21 at 19:16
What do you want your function to return when the element is not found? — n. m. could be an AI, May 21 '21 at 19:19
Side note: When you have a consistent crash, see if you can reproduce it in a debug build. If you can, then narrowing down the cause, or even zoom right in on it, with a debugger is almost child's play. Run the program in the debugger. Wait for the crash. Investigate the the variables involved and the backtrace so see how you got there. Use the information gathered to improve your test cases and decide where to look next. — user4581301, May 21 '21 at 19:20
@Rishav Kumar There is a typo in this if statement if(r>=1){ there shall be if(r>=l){ — Vlad from Moscow, May 21 '21 at 19:23

score 0 · Accepted Answer · answered May 21 '21 at 19:15

The condtion r>=1 should be r-l+1>=1 to check if there are some element in the range.
The initialization int mid=(r-1)/2+l; should be int mid=(r-l)/2+l; to correctly calculate the middle element.
Variable-Length Array int x[n]; is not in the standard C++. You should use heap allication int *x = new int[n]; instead. After that, n should be used for the initialization of t because the technique to obtain the number of elements in arrays won't work with pointers.

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

int binarySearch(int x[],int l, int r, long int m ){
    if(r-l+1>=1){
        int mid=(r-l)/2+l;
        if (x[mid]==m) return mid;
        if (x[mid]>m) return binarySearch(x,l,mid-1,m);
        if (x[mid]<m) return binarySearch(x,mid+1,r,m);
    }
    return 0;
}
int main(){
    int n,q;
    cin>>n;
    int *x = new int[n];
    for(int i=0;i<n;i++){cin>>x[i];}
    int t = n;
    sort(x,x+t);
    cin>>q;
    while (q--){
        long int m;
        cin>>m;
        cout<<binarySearch(x,0,t-1,m)<<endl;
        
    }
    
    
    delete[] x;
    return 0;
}

Addendum: if allowed by the assignment, replacing `int *x = new int[n];` with `std::vector x(n);` to simplify the memory management can be very attractive. Using `std::vector` as your first choice for a dynamically sized array is highly recommended. — user4581301, May 21 '21 at 19:25
@user4581301 I agree, and `binarySearch(x,0,t-1,m)` should be `binarySearch(x.data(),0,t-1,m)` in that case. — MikeCAT, May 21 '21 at 19:27

segmentation fault in recursive binary searching

1 Answers1