What am I doing wrong in my C binary search code?

Question

I am working on a binary search algorithm in preparation for my coding interview, my algorithm is however working only for the best-case scenario, that is, when the searched data is at the midpoint, O(1). The cursor is stuck when I change the value to a worse case, like the first position.

I know that binary search has an O(log n) worse case so it should not take long. Am I doing it wrong?

#include <stdio.h>

int binary_search(int arr[], int left, int right, int data){
    // condition that runs only if true
    while(left <= right){
        int mid = (left + right) / 2;
        if(data == arr[mid]){
            return mid;
        }

        if(data > arr[mid]){
            binary_search(arr, mid+1, right, data);
        }

        binary_search(arr, left, mid-1, data);
    }
    return -1;
}

void main(){
    int arr[] = {1,2,3,4,5,6,7,8,9};
    int result = binary_search(arr, 0, (sizeof(arr)/sizeof(arr[0]) - 1), 2);
    (result == -1) ? printf("There was no record found\n") : printf("Your record was found at position %d\n", result+1);
}

Answer 1

You are triggering infinite recursion by not returning properly from your function. Where you call binary_search(arr, mid+1, right, data); recursively, you need to propagate the return value back to the calling function.

Also, irrelevant to your problem but in C void main() is technically not legal, even though you may not get any explicit errors. main() should return an int always.

#include <stdio.h>

int binary_search(int arr[], int left, int right, int data){
    // condition that runs only if true
    while(left <= right){
        int mid = (left + right) / 2;
        if(data == arr[mid]){
            return mid;
        }

        if(data > arr[mid]){
            return binary_search(arr, mid+1, right, data);
        }

        return binary_search(arr, left, mid-1, data);
    }
    return -1;
}

int main(void){
    int arr[] = {1,2,3,4,5,6,7,8,9};
    int result = binary_search(arr, 0, (sizeof(arr)/sizeof(arr[0]) - 1), 2);
    (result == -1) ? printf("There was no record found\n") : printf("Your record was found at position %d\n", result+1);

    return 0;
}