Infinite recursion: binary search & asserts

Question

I'm writing an implementation of binary search in C and I'm getting infinite recursion for no apparent (to me) reason. Heres my code:

/*Orchestrate program*/
int main(int argc, char* argv){
    int array[] = {1,2,3,3,3,6,7,8,9,9,20,21,22};
    int length = 13;
    int key = 23;
    binary_search(key, array, 0, length - 1);
    return 0;
}

int binary_search(int key, int array[], int first_index, int last_index){
    int middle;
    middle = (first_index + last_index)/2;
    if (first_index == last_index){
        if (array[middle] == key){
            printf("%d has been found at position %d\n", key, middle+1);
        }
        printf("item not found");
    }
    else if (key > array[middle]){
        binary_search(key, array, middle, last_index);
    }
    else if (key < array[middle]){
        binary_search(key, array, first_index, middle);
    }
}

Based on the value of my key in main, I guess the problem lies in the first else if, but I'm not sure why. If I were to remove the first_index == last_index line, the algorithm works fine but only when the item is in the array. If the item isn't in the array, I naturally get infinite recursion.

Also, I tried to fix this problem by removing the first_index == last_index line and placing a return -1; at the end of the function, but I get the same problem that I am getting now.

EDIT:

Putting together pieces of advice I received from a few different users, I came to the following solution (fixed off by one errors and un-nested decisions):

void binary_search(int key, int array[], int first_index, int last_index){
    int middle;
    middle = (first_index + last_index)/2;

    if (array[middle] == key){
        printf("%d has been found at position %d\n", key, middle+1);
    }
    if (first_index == last_index){
        printf("item not found");
    }
    else if (key > array[middle]){
        binary_search(key, array, middle + 1, last_index);
    }
    else if (key < array[middle]){
        binary_search(key, array, first_index, middle - 1);
    }
}

I have a follow-up question: Could there have been a way to use asserts to assist me in finding this solution myself? (I'm just learning about asserts so I'm wondering where I can apply them)

Answer 1

Your function should look like this:

void binary_search(int key, int array[], int first_index, int last_index){
    int middle;
    middle = (first_index + last_index)/2;
    if (array[middle] == key){
        printf("%d has been found at position %d\n", key, middle+1);
    }
    else if (first_index == last_index) {
         printf("item not found");
    }
    else if (key > array[middle]){
        binary_search(key, array, middle + 1, last_index);
    }
    else {
        //assert (key < array[middle]); // feel free to uncomment this one and include the assert library if you want
        binary_search(key, array, first_index, middle - 1);
    }
}

In other words, increment or decrement middle appropriately in the recursive call.

This is important, because, for example, when you reduce to size 2 for your search and middle is your first element, then effectively you are not changing the dimension of the array in the recursive calls.

I also changed your function to void since you are not returning anything.

Answer 2

You search ever smaller ranges of a sorted array. The bounadries of your array are inclusive.

The base case of your recursion is: If the range is empty, the key is not found. Or, in code:

if (first_index > last_index){
    printf("Not found\n");
}

You should calculate and compare the middle element of your range only after you have established that the range is not empty. In that case, you have three outcomes:

• The middle element is the key: bingo!
• The middle element is smaller than the key: Search the right half of the array and exclude the middle element, which we have already checked.
• The middle element is larger than the key: Ditto, but with the left half.

Putting this all together:

void binary_search(int key, int array[], int first_index, int last_index)
{
    if (first_index > last_index){
        printf("Not found\n");
    } else {
        int middle = (first_index + last_index) / 2;

        if (array[middle] == key) printf("%d at index %d\n", key, middle);

        if (key > array[middle]){
            binary_search(key, array, middle + 1, last_index);
        } else {
            binary_search(key, array, first_index, middle - 1);
        }
    }
}

This function still has two things that nag me:

• A function that prints the index is of little practical use. The printing should be done by the client code, i.e. by the code that calls the function. Return the found index or a special value for "not found" instead.
• The range has inclusive bounds. That's not very C-like. In C, a range is usually described by an inclusive lower and an exclusive upper bound. That's how array indices and for loops work. Following this convention means that your client code doesn't have to do the awkward length - 1 calculation.

So here's a variant that returns the index or -1 if the key is not in the array:

int binary_search1(int key, int array[], int first_index, int last_index)
{
    if (first_index < last_index){
        int middle = (first_index + last_index) / 2;

        if (array[middle] == key) return middle;

        if (key > array[middle]){
            return binary_search1(key, array, middle + 1, last_index);
        } else {
            return binary_search1(key, array, first_index, middle);
        }
    }

    return -1;
}

and test it with:

int main()
{
    int arr[6] = {3, 4, 6, 8, 12, 13};
    int i;

    for (i = 0; i < 20; i++) {
        int ix = binary_search(i, arr, 0, 6);

        if (ix < 0) {
            printf("%d not found.\n", i);
        } else {
            printf("%d at index %d.\n", i, ix);
        }
    }

    return 0;
}

Note that your original array has duplicate entries. This is okay, but you will get the index of any of the duplicate values, not necessarily the first one.