Binary Search in C - Stuck in a loop

Question

I'm currently trying to write a program which takes an array of numbers and sorts them into a new array using a binary search method. Right now, I'm stuck in an infinite loop because: if( &arr[mid_val] != NULL) keeps returning true, even though I've initialized int *arr as NULL .

Why is this the case? Should it not return false on the first iteration?

Code:

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

int binary_search( int *arr, int to_find, int size ) {
    int mid_val;
    int new_size;
    int return_val;
    int *new_arr;

    mid_val = size / 2;

    printf("infinite\n");

    if( &arr[mid_val] != NULL ) {    /* why does this return true in the first iteration? */
        if( to_find > arr[mid_val] ) {
            /* second half of arr */
            new_arr = malloc( sizeof( int ) * ( mid_val ) );
            memcpy( new_arr, &arr[mid_val], sizeof( int ) * ( mid_val ) );
            new_size = mid_val;

            return_val = mid_val + binary_search( new_arr, to_find, new_size );

            return return_val;
        }
        else if( to_find < arr[mid_val] ) {
            /* first half of arr */
            new_arr = malloc( sizeof( int ) * ( mid_val ) );
            memcpy( new_arr, arr, sizeof( int ) * ( mid_val ) );
            new_size = mid_val;

            return_val = binary_search( new_arr, to_find, new_size );

            return return_val;
        }
    }
    return 0;
}

int main ( ) {
    int i;
    int pos;
    int size = 0;
    int numbers[10] = { 5, 8, 12, 2, 1, 0, 9, 22, 21, 55 };
    int *arr = NULL;

    for( i = 0; i < 10; i++) {
        arr = realloc( arr, sizeof( int ) * ( size + 1 ) );

        pos = binary_search( arr, numbers[i], size );

        memcpy( &arr[pos + 1], &arr[pos], ( size - pos ) * sizeof( int ) );
        memcpy( &arr[pos], &numbers[i], sizeof( int ) );

        size++;
    }

    for(i = 0; i < size; i++){
        printf("%d\n", arr[i]);
    }

    return 0;
}

Answer 1

You are leaking memory like a broken water pipe.

if( &arr[mid_val] != NULL ) {    /* why does this return true in the first iteration? */

This is always true, except when mid_val is 0 and arr is NULL. The expression arr[mid_val] is equivalent to arr + mid_val, which when mid_val is not 0 will return you the address where arr pointing plus the offset mid_val * sizeof(*arr).

What you have to do is first check that arr is not NULL. If it is NULL then return an error value.

int binary_search( int *arr, int to_find, int size ) {
    ...

    if(arr == NULL)
        return -1;  // negative index == error
}

In this block:

new_arr = malloc( sizeof( int ) * ( mid_val ) );
memcpy( new_arr, &arr[mid_val], sizeof( int ) * ( mid_val ) );
new_size = mid_val;

return_val = mid_val + binary_search( new_arr, to_find, new_size );

return return_val;

you are allocating memory for the copy of the array of half size. But you never free the memory, that's where your code is leaking. You should do:

return_val = mid_val + binary_search( new_arr, to_find, new_size );

free(new_arr);
return return_val;

If your search does not find anything, you should return -1. 0 is a valid index, how can you distinguish between and error and a valid index?

Also you don't have a real terminal case for the iteration, eventually mid_val will reach 0 and you will keep calling malloc with size 0. The recursion will only end when malloc returns NULL or you've reached the limits of recursion. In both cases you've consumed so much resources, that the system kills your program or it ends in a segfault.

Note that malloc(0) does not necessarily return NULL.

man malloc

#include <stdlib.h>

void *malloc(size_t size);

RETURN VALUE

The malloc() and calloc() functions return a pointer to the allocated memory, which is suitably aligned for any built-in type. On error, these functions return NULL. NULL may also be returned by a successful call to malloc() with a size of zero, or by a successful call to calloc() with nmemb or size equal to zero.

It says may, not will. Other sources say:

http://pubs.opengroup.org/onlinepubs/009695399/functions/malloc.html

The pointer returned points to the start (lowest byte address) of the allocated space. If the space cannot be allocated, a null pointer shall be returned. If the size of the space requested is 0, the behavior is implementation-defined: the value returned shall be either a null pointer or a unique pointer.

In any case, you cannot relay for a terminal case that malloc returns NULL when you request 0 bytes.

But the biggest problem of all in your code is that the binary search algorithm is design to work on sorted arrays. If the array is not sorted, then searching only in the space before/after the mid-element makes no sense, as there would be no guarantee that all element after the mid-element are larger and all elements before the mid-element are respectively smaller. Your initial array is not sorted, binary search is pointless.

I think that using malloc for a binary search is quite a waste of resources, all you need is to pass the start and end of the search space. This is a possible implementation of the binary search, note that the array is sorted to begin with. There are tons of example implementations of this on the internet, a simple Google search shows in the first page some version.

#include <stdio.h>
#include <string.h>

int binary_search(int *arr, int to_find, size_t start, size_t end)
{
    if(arr == NULL)
        return -1;

    if(start == end)
    {
        if(arr[start] == to_find)
            return start;

        return -1; // not found
    }


    int index;
    int mid = start + (end - start) / 2;

    if(arr[mid] == to_find)
        return mid;

    if(to_find < arr[mid])
        index = binary_search(arr, to_find, start, mid - 1);
    else
        index = binary_search(arr, to_find, mid + 1, end);

    return index;
}


int main(void)
{
    int numbers[] = { -19, -17, -3, 0, 5, 9, 12, 13, 14, 18, 20, 44, 77, 122, 888 };

    size_t arrlen = sizeof numbers / sizeof *numbers;

    int index;
    int search[] = { -19, -17, -3, 0, 5, 9, 12, 13, 14, 18, 20, 44, 77, 122, 888, 32, 50 };

    for(size_t i = 0; i < sizeof search / sizeof *search; ++i)
    {
        index = binary_search(numbers, search[i], 0, arrlen - 1);

        if(index == -1)
            printf("Number %d not found\n", search[i]);
        else
            printf("Number %d found at index: %d\n", search[i], index);
    }

    return 0;
}

The output is

Number -19 found at index: 0
Number -17 found at index: 1
Number -3 found at index: 2
Number 0 found at index: 3
Number 5 found at index: 4
Number 9 found at index: 5
Number 12 found at index: 6
Number 13 found at index: 7
Number 14 found at index: 8
Number 18 found at index: 9
Number 20 found at index: 10
Number 44 found at index: 11
Number 77 found at index: 12
Number 122 found at index: 13
Number 888 found at index: 14
Number 32 not found
Number 50 not found

Answer 2

if( arr[mid_val] != NULL) keeps returning true, even though I've initialized int *arr as NULL

If arr is NULL, you are dereferencing a null pointer. You need to allocate memory for arr to point to and initialize the contents of that memory.

Note that int *arr represents the array you want to search. If it is null, you have nothing to search.

You may have meant to say that you allocated memory for arr and filled the memory with something... zero's? Filling it with NULL doesn't make sense. As @lurker pointed out in the comments, comparing an integer to NULL likely isn't what you intend.