Reputation: 1
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;
}
Upvotes: 0
Views: 149
Reputation: 13600
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()
andcalloc()
functions return a pointer to the allocated memory, which is suitably aligned for any built-in type. On error, these functions returnNULL
.NULL
may also be returned by a successful call tomalloc()
with a size of zero, or by a successful call tocalloc()
withnmemb
orsize
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
Upvotes: 1
Reputation: 150238
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.
Upvotes: 0