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

Your code is not working because your recursive function returns nothing if in the first iteration data is not equal to arr[mid]. So in such a case you will have an infinite recursion.

But in any case for a professional programmer the code is very and very weak.

For example your function may not be called for a constant array. (Is one more function with a different name required?)

The function should have only three parameters

return_type binary_search( const int a[], size_t n, int data );

If the function returns an index of the target element then its return type should be size_t because in general the type int can be unable to accommodate a value of the expression sizeof( a ) / sizeof( *a ).

If the function only checks whether a given value exists in the array then it should return either 0 or 1 and its return type should be either int or or _Bool.

If the function should return a position of the target value then it should return the first position of the element with the target value the same way as the standard algorithm std::lower_bound in C++ does.

It is not a good idea to copy the same drawback of the standard C function bsearch that in general does nor return the position of the first element with the target value.

You shall not use the operator == to compare values (though comparison functions in C use this operator) because for example for floating numbers you can get a wrong result. You should use only the operator <.

Well, let's assume that your function works for arrays with the element type int and the operator <. But what to do if the user wants to use its own comparison function for elements of array?

And the second problem if the user is going to use an array with the element type long long or an array of structures does he need to spend his time to write one more binary search function?

My advice: never do any assignments in an interview. Ignore firms that try to manipulate you and your time. Interview is a conversation of equal partners. During a simple conversation it is easy to understand "who is who" provided that you are yourself a qualified programmer. :)

Answer 2

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