H. Ahmed H. Ahmed - 4 months ago 37
C Question

returning boolean from a recursive binary search in C

I am trying to implement a recursive binary search in C. I am using the CS50 library to define bool as a type. My code will find the inputted value in a test array. However when i check the returned value r with an if statement it is usually returning false, even though the number is found.My code is as follows:

#include <stdio.h>
#include <cs50.h>

bool binarysearch(int value, int values [], int n, int lo, int hi);
int main(void)
{
// test array of 6 values sorted.
int values[] = {1 , 2, 3, 4 , 5, 6};
int n = 6;
int hi = values[n-1];
int lo = values[0];
// input from user
printf("What number\n");
int value = GetInt();
//search for value in test arary
bool r = binarysearch(value,values,n,lo,hi);
if (!r)
{
printf("not right\n");
return 1;
}
return 0;
}

bool binarysearch(int value, int values [], int n, int lo, int hi)
{
int mid;
mid = (lo + hi)/2;
// condition to avoid indexing error
if (((mid == 0) || (mid == n-1)) && (values[mid] != value) )
{
return false;
}
//check if value is at mid index in test array
if (values[mid] == value)
{
printf("Key Found\n");
return true;
}
// check right half of array
else if(value > values[mid])
{
binarysearch(value, values,n, mid+1, hi);
}
// check left half of array
else if(value <values[mid])
{
binarysearch(value, values,n,lo, mid-1);
}
return false;
}

Answer

This example will perform a binary search and return a boolean, similar to your code but the algorithm has to be correct.

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

bool binarysearch(int value, int values[], int n, int lo, int hi) {
    int mid = (hi + lo) / 2;
    if (lo <= hi) {
        if (values[mid] == value) {
            printf("Key found at index %d \n", mid);
            return true;
        }
        else if (values[mid] > value)
            return binarysearch(value, values, n, lo, mid);
        else
            return binarysearch(value, values, n, mid + 1, hi);;
    }
    else return 0;
}

main() {
    int i, n, value;
    int values[] = {1, 2, 3, 4, 5, 6};

    int hi = values[n - 1];
    int lo = values[0];
    printf("What number? \n");
    scanf("%d", &value);

    if (!binarysearch(value, values, n, 0, 5))
        printf("Number not present in array\n");
}

You can try this algorithm online using random integer between 1 and 13 making it a 50 % chance of finding the number if you follow the link.