Binary search implementation in C

Question

First time posting here. I recently implemented Binary Search but sometimes my outputs will return a giant negative number instead. Now my first thought is that I'm printing a number where my pointer is pointing at a random memory location. Can someone help me with the logic and how I can improve my code?

#include <stdio.h>
#include <stdlib.h>

int binarysearch(int *array, int size, int target);

int main() {
    int array[] = { 1, 2, 3, 4, 5, 6 };
    printf("%d\n", binarysearch(array, 8, 15));
    return 0;
}

int binarysearch(int *array, int size, int target) {
    int mid;    
    mid = size / 2;

    if (size < 1) {
        return -1;
    }
    if (size == 1) {
        return array[0];
    }
    if (target == array[mid]) {
        return target;
    } else
    if (target < array[mid]) {
        binarysearch(array, mid, target);
    } else{
        binarysearch(array + mid, size - mid, target);
    }
}

Answer 1

For starters you call the function with an invalid number of elements in the array that has only 6 elements.

int array[] = { 1, 2, 3, 4, 5, 6 };
printf("%d\n", binarysearch(array, 8, 15));
                                  ^^^

Also this snippet

if (size == 1) {
    return array[0];
}

is incorrect. It is not necessary that the first element is equal to target.

This statement

    binarysearch(array + mid, size - mid, target);

has to be written like

    binarysearch(array + mid + 1, size - mid - 1, target);

And at last the function has undefined behavior because it returns nothing in these cases

if (target < array[mid]) {
    binarysearch(array, mid, target);
} else{
    binarysearch(array + mid, size - mid, target);
}

You need to write

if (target < array[mid]) {
    return binarysearch(array, mid, target);
} else{
    return binarysearch(array + mid, size - mid, target);
}

And two words about the programming style. It is better to name the function either like binary_search or like binarySearch or at last like BinarySearchthan like binarysearch.

In general it is not a good design of the function. Imagine that the array has an element with the value -1. How will you determine whether this element is present in the array or is absent?

Usually such functions return pointer to the target element in case if it is found or NULL pointer otherwise.

Here is a demonstrative program that shows how this approach can be implemented.

#include <stdio.h>

int * binary_search( const int *a, size_t n, int target ) 
{
    if ( n == 0 ) return NULL;

    size_t middle = n / 2;

    if ( a[middle] < target )
    {
        return binary_search( a + middle + 1, n - middle - 1, target );
    }
    else if ( target < a[middle] )
    {
        return binary_search( a, middle, target );
    }

    return a + middle;
}

int main(void) 
{
    int array[] = { 1, 2, 3, 4, 5, 6 };
    const size_t N = sizeof( array ) / sizeof( *array );

    for ( int i = 0; i < 8; i++ )
    {
        int *target = binary_search( array, N, i  );
        if ( target )
        {
            printf( "%d is found at position %d\n",  *target, ( int )(target - array ) );
        }
        else
        {
            printf( "%d is not found\n", i );
        }
    }

    return 0;
}

The program output is

0 is not found
1 is found at position 0
2 is found at position 1
3 is found at position 2
4 is found at position 3
5 is found at position 4
6 is found at position 5
7 is not found

By the way according to the C Standard function main without parameters shall be declared like

int main( void )

Answer 2

You call binarysearch(array, 8, 15)) but your array has only 6 entries.

Here is how to compute the proper size automatically:

int main(void) {
    int array[] = { 1, 2, 3, 4, 5, 6 };
    printf("%d\n", binarysearch(array, sizeof(array) / sizeof(array[0]), 15));
    return 0;
}

Note that your function binarysearch has problems too:

1. Returning the array entry is bogus, what do you return if the target is less than the first entry? -1 is not necessarily less than the first entry.

2. You are supposed to return the index into the array with the entry if found and -1 if not found.

3. When you recurse, you do not return the value from these recursive calls: you should compile with warnings enabled (for example: gcc -Wall -W) and look at all the helpful diagnostic messages the compiler produces.

Here is a modified version:

int binarysearch(const int *array, int size, int target) {

    int a, b;

    for (a = 0, b = size; a < b;) {
        int mid = a + (b - a) / 2;
        if (target <= array[mid]) {
            b = mid;
        } else {
            a = mid + 1;
        }
    }
    // a is the offset where target is or should be inserted
    if (a < size && target == array[a])
        return a;
    else
        return -1;
}

Notes:

• Computing mid = (a + b) / 2; would be potentially incorrect for large sizes as there may be an arithmetic overflow. mid = a + (b - a) / 2; does not have this problem since a < b.

• The time-complexity is O(Log N), and for a given size, the function performs the same number of steps for all target values.

• If the array contains multiple identical values equal to target, the index returned by binarysearch is that of the matching entry with the lowest index.

Answer 3

You could make this problem easier by using the bsearch function offered by the <stdlib.h> library.

Something like this:

#include <stdio.h>
#include <stdlib.h>

int cmpfunc(const void * a, const void * b);

int
main(void) {
    int array[] = {1, 2, 3, 4, 5, 6};
    size_t n = sizeof(array)/sizeof(*array);
    int *item;
    int key = 15;

    item = bsearch(&key, array, n, sizeof(*array), cmpfunc);

    if (item != NULL) {
        printf("Found item  = %d\n", *item);
    } else {
        printf("Item = %d could not be found\n", key);
    }

    return 0;
}

int 
cmpfunc(const void * a, const void * b) {
   return (*(int*)a > *(int*)b) - (*(int*)a < *(int*)b);
}

If you don't want to use bsearch, then this method will be fine also:

#include <stdio.h>
#include <stdlib.h>

#define BSFOUND 1
#define BS_NOT_FOUND 0

int cmpfunc(const void * a, const void * b);
int binary_search(int A[], int lo, int hi, int *key, int *locn);

int
main(void) {
    int array[] = {1, 2, 3, 4, 5, 6};
    size_t n = sizeof(array)/sizeof(*array);
    int key = 4, locn;

    if ((binary_search(array, 0, n, &key, &locn)) == BSFOUND) {
        printf("Found item = %d\n", array[locn]);
    } else {
        printf("Item = %d cound not be found\n", key);
    }

    return 0;
}

int
binary_search(int A[], int lo, int hi, int *key, int *locn) {
   int mid, outcome;

   if (lo >= hi) {
      return BS_NOT_FOUND;
   }

   mid = lo + (hi - lo) / 2;
   if ((outcome = cmpfunc(key, A+mid)) < 0) {
      return binary_search(A, lo, mid, key, locn);
   } else if(outcome > 0) {
      return binary_search(A, mid+1, hi, key, locn);
   } else {
      *locn = mid;
      return BSFOUND;
   }
}

int 
cmpfunc(const void * a, const void * b) {
   return (*(int*)a > *(int*)b) - (*(int*)a < *(int*)b);
}