Trouble figuring out the problems with recursive binary search in C

Question

I am having trouble understanding why my code is returning segmentation errors when I test it. I am trying to learn recursion, and C and I would be grateful if someone could show me where I am wrong. Here it is:

// Binary search through numbers using recursion.
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <ctype.h>
#include <stdlib.h>

//prototype
bool search(int n, int array[], int lower, int upper);

int main(void) {
    int elements;
    //getting a list of numbers from the user
    printf("How many elements are in the array?:");
    scanf("%d", &elements);
    printf("Please type the elements:");
    int array[elements];
    for (int i = 0; i < elements; i++)
        scanf("%d", &array[i]);

    //printing out the array elements typed
    printf("The array is: ");
    for (int k = 0, arraylen = elements; k < arraylen; k++)
        printf("%d ", array[k]);
    printf("\n");
    printf("What number do you wish to search?");
    int item;
    scanf("%d", &item);
    bool result = search(item, array, array[0], array[elements]);
    if (result) {
        printf("Number found.\n");
    } else {
        printf("Number not found.\n");
    }
    return 0;
}

bool search(int n, int array[], int lower, int upper) {
    //base case
    if (upper < lower) {
        return false;
    }

    int midpoint = (upper + lower) / 2;
    if (n == array[midpoint]) {
        return true;
    }
    /** If value searched for is greater than the value at midpoint,  then
        Then discard everything to the left of a sorted list. **/
    else if (n > array[midpoint]) {
        //lower becomes midpoint + 1
        return search(n, array, (midpoint + 1), upper);
    }
    /** If value searched for is less than the value at midpoint, then
        Then discard everything to the right of a sorted list. **/    
    else if (n < array[midpoint]) {
        //upper becomes midpoint - 1
        return search(n, array, lower, (midpoint - 1));
    }
}

When I run it, this happens:

./bin_search 
How many elements are in the array?:5
Please type the elements:1 2 3 45 46
The array is: 1 2 3 45 46 
What number do you wish to search?45
Segmentation fault (core dumped)

Answer 1

Try this code I did nt try this you can call the following function

bool result = search(item, array, 0, lenth_of_array - 1); 

search function like this

bool search(int item, int array[], int start, int end){

   if(start>end){
      return false;
   }
   int mid = (start+end)/2;
   if(array[mid]==item){
       return true;
   }

   else if(array[mid]>item){
       return search(item, array, start, mid-1);
   }

   else if(array[mid]<item){
       return search(item, array,mid+1,end);
   }

}

Answer 2

lower and upper should be indexes, instead of values.

// Binary search through numbers using recursion.

#include <stdio.h>
#include <stdbool.h>

//prototype
bool search(int n, int array[], int lower, int upper);

int main(void) {
    int elements;
    //getting a list of numbers from the user
    printf("How many elements are in the array?:");
    scanf("%d", &elements);
    printf("Please type the elements:");
    int array[elements];
    for (int i = 0; i < elements; i++)
        scanf("%d", &array[i]);

    //printing out the array elements typed
    printf("The array is: ");
    for (int k = 0, arraylen = elements; k < arraylen; k++)
        printf("%d ", array[k]);
    printf("\n");
    printf("What number do you wish to search?");
    int item;
    scanf("%d", &item);
    bool result = search(item, array, 0, elements-1);
    if (result) {
        printf("Number found.\n");
    } else {
        printf("Number not found.\n");
    }
    return 0;
}

bool search(int n, int array[], int lower, int upper) {
    if (upper < lower) {
        return false;
    }

    int midpoint = (upper + lower) / 2;

    if (n == array[midpoint]) {
        return true;
    }
    else if (n > array[midpoint]) {
        search(n, array, (midpoint + 1), upper);
    }
    else {
        search(n, array, lower, (midpoint - 1));
    }
}

And the reason why you got a segfault is that array[array[5]] may be beyond the scope of array, whose type is int (*)[5], causing undefined behavior.(In fact, dereferencing array[5] itself causes undefined behavior, as pointed out by chqrlie.)

Answer 3

You should pass the array boundary indices, not the elements:

bool result = search(item, array, 0, elements);

Your current code invokes undefined behavior: search(item, array, array[0], array[elements]) passes array[elements] as the upper boundary, reading past the end of the array, probably a very large number that causes the search function to reference an invalid address, causing the Segmentation fault.

Also these boundaries are not handled correctly in the search function: upper is excluded, so the initial test should be if (upper <= lower) return false;, and when you recurse on the left half, you should use midpoint as the upper boundary, not midpoint-1.

Here is a corrected version:

bool search(int n, int array[], int lower, int upper) {
    //base case
    if (upper <= lower)
        return false;

    int midpoint = (upper + lower) / 2;
    if (n == array[midpoint])
        return true;

    /** If value searched for is greater than the value at midpoint,  then
        Then discard everything to the left of a sorted list. **/
    if (n > array[midpoint]) {
        //lower becomes midpoint + 1
        return search(n, array, midpoint + 1, upper);
    }
    /** If value searched for is less than the value at midpoint, then
        Then discard everything to the right of a sorted list. **/    
    //upper becomes midpoint - 1
    return search(n, array, lower, midpoint);
}

Note that you need a way to know the index for the match, a solution would be to return this index and return -1 for no match.