Checking if an element is in the array or not infinite loop

150 views Asked by At

I'm trying to see if a number is in the array or not in logn time but this function executes

else if(arr[(r-l)/2] < n) 

all the time and it becomes an infinite loop. Why is that?

int exists(int n, int *arr, int l, int r){
    if(l == r){

        if(arr[l] == n){
            return 1;
        }
        else{
            return 0;
        }
    }
    else if(arr[(r-l)/2] == n){
        return 1;
    }
    else if(arr[(r-l)/2] > n){
        return exists(n, arr, l, (r-l)/2);
    }
    else if(arr[(r-l)/2] < n){
        return exists(n, arr, (r-l)/2, r);
    }
}

int main(){
    node *root = NULL;

    int arr[5] = {1,2,3,4,5};
    printf("%d", exists(5, arr, 0, 4));

}
1

There are 1 answers

4
Stephen Docy On

well, if

else if (arr[(r-l)/2] == n) {

is being executed, then it is because

if (l == r) {

is false

It looks like you are trying to do a binary search, if so, your index computations are all wrong.

int exists(int n, int *arr, int l, int r) {
    if (l <= r) {
        int mid = (l + r) / 2;
        if (arr[mid] == n) {
            return 1;
        } else if (arr[mid] > n) {
            return exists(n, arr, l, mid - 1);
        } else {
            return exists(n, arr, mid + 1, r);
        }
    }

    return 0;
}