### Thread: C Puzzle of the week/month/year (2009-12-08)

Page 1 of 2 12 Last
1. #### C Puzzle of the week/month/year (2009-12-08)

Right guys, it is time for another puzzle of the week/month/year. Today's code is a simple binary search function written in C:
Code:
```int binary_search(int *array, int target, int low, int high)
{
int middle;

if (low >= high)
return 0;

middle = (low + high) / 2;

if (target == array[middle])
return 1;
else if (target < array[middle])
return binary_search(array, target, low, middle);
else
return binary_search(array, target, middle + 1, high);
}```
As you can see, the function looks for target within array. The assumptions made by this function are that array is already sorted and low and high are valid. There is however a serious bug in this function. Your task for this week is to (a) identify the bug and (b) propose a fix.

Usual puzzle of the week rules apply: I'll post the solution on Friday, if no one has proposed the answer by then. As before, winners have the privilege of having their names appear in green font under my signature for an unspecified period of time.
Last edited by Scorpions4ever; December 8th, 2009 at 07:08 PM.
2. This seems to work for me:

Code:
```int binary_search(int *array, int target, int low, int high){
int middle = ((low + high) / 2);;
if (low > high) return 0;

if (target == array[middle])
return 1;
else if (target < array[middle])
return binary_search(array, target, low, middle - 1);
else
return binary_search(array, target, middle + 1, high);
}```
It appears that the low <= high was the problem as when it was equal it was failing to do the test.
3. Not quite sir. To be fair, I edited my original code a bit and changed this line:
Code:
```    else if (target < array[middle])
return binary_search(array, target, low, middle - 1);```
to:
Code:
```    else if (target < array[middle])
return binary_search(array, target, low, middle);```
and the edit might have happened when you were looking at the code. If you have my correction, the if (low >= high) statement is correct.

I'd originally swiped the code from a sample in dreamincode and the author had got it wrong ALONG with the bug I'm looking for. I corrected the one bug which was the one you pointed out. The other one is still there. It is actually very hard to get a decent binary search right.

Here's a more generic version that has the same bug:
Code:
```int binary_search(void *array, void *target, compare_fn compare, int elem_size, int low, int high)
{
int middle;
int cmp_result;
void *ptr;

if (low >= high)
return 0;

middle = (low + high) / 2;

ptr = array + middle * elem_size;
cmp_result = compare(target, ptr);

if (cmp_result == 0)
return 1;
else if (cmp_result < 0)
return binary_search(array, target, compare, elem_size, low, middle);
else
return binary_search(array, target, compare, elem_size, middle + 1, high);
}```
and you can use it like this (for instance, to check entries in an array of int):
Code:
```int compare_int(void *a, void *b)
{
int x = *(int *)a;
int y = *(int *)b;
if (x < y)
return -1;
else if (x > y)
return 1;
return 0;
}

#define MAX_SIZE  10

int main(void)
{
int array[MAX_SIZE];
int i;
int max_len = sizeof(array) / sizeof(array[0]);
for (i = 0; i < MAX_SIZE; i++)
array[i] = i + 1;

for (i = 1; i < MAX_SIZE + 1; i++) {
printf("Checking %d: %d\n", i, binary_search(array, &i, compare_int, sizeof(int), 0, max_len));
}

i = -1;
printf("Checking %d: %d\n", i, binary_search(array, &i, compare_int, sizeof(int), 0, max_len));
i = 42;
printf("Checking %d: %d\n", i, binary_search(array, &i, compare_int, sizeof(int), 0, max_len));

return 0;
}```
This is a more generic version which can be used with arrays of any object. Can you spot the bug?

Fixed the one typo (size / elem_size) pointed out below[/edit]
Last edited by Scorpions4ever; December 9th, 2009 at 12:11 PM.
4. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Dec 2009
Posts
16
Rep Power
0
is it change
Code:
`middle = (high + low)/2;`
to
Code:
`middle = low + (high - low)/2;`
due to overflow with large arrays?

• mike65535 agrees : Nice
5. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Jan 2009
Posts
337
Rep Power
46
Is it overflow of (low + high)???
6. No Profile Picture
Contributing User
Devshed Loyal (3000 - 3499 posts)

Join Date
May 2004
Posts
3,417
Rep Power
887
Originally Posted by scorpions4ever
Here's a more generic version that has the same bug:
It's not even compilable.

binary_search(array, target, compare, size, low, middle);

should probably be:

binary_search(array, target, compare, elem_size, low, middle);

I should probably know this, but does C allow doing arithmetic on void pointers? I had to change:

ptr = array + middle * elem_size

to:

ptr = (void*)((char*)array + middle * elem_size);

to get it to compile in my usual cpp file that I use for testing devshed stuff.

Last edited by jwdonahue; December 9th, 2009 at 11:34 AM.
7. No Profile Picture
Contributing User
Devshed Loyal (3000 - 3499 posts)

Join Date
May 2004
Posts
3,417
Rep Power
887
Originally Posted by Scorpions4ever
Usual puzzle of the week rules apply
Where can we find those?
8. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Jan 2009
Posts
337
Rep Power
46
ptr = (void*)((int*)array + middle * elem_size);

Shouldn't it be
(char*) array + middle * elem_size
??
9. No Profile Picture
Contributing User
Devshed Loyal (3000 - 3499 posts)

Join Date
May 2004
Posts
3,417
Rep Power
887
Originally Posted by Nyan
ptr = (void*)((int*)array + middle * elem_size);

Shouldn't it be
(char*) array + middle * elem_size
??
Doh! I pasted the wrong line in there. Not thinking. I noticed elem_size was one of the factors and actually removed cast to int* from the function I was testing, but must have already had the other one in my clipboard. I initially had the first binary_search() in mind that only worked with ints. Thanks for catching that Nyan. I'll go edit the post.
10. JW, how come you quoted me in post #6? Scorp and I are not the same person.
11. No Profile Picture
Contributing User
Devshed Beginner (1000 - 1499 posts)

Join Date
Jul 2004
Location
Middle Europa
Posts
1,200
Rep Power
14
hallo scorpion
i did NOT analized your code
IMHO
an 'else' after a 'if(..) return' is a STUPIDITY
so
Code:
```           if(...) return(x);
return(0);```
that 'else' will never be reached if the 'if' statement is true, so :(:(:(
Code:
```            if(...) return(x);
return(0);```
this is logic .... just a finesse!
12. No Profile Picture
Contributing User
Devshed Beginner (1000 - 1499 posts)

Join Date
Jul 2004
Location
Middle Europa
Posts
1,200
Rep Power
14
hallo scorpion and all other gurus in this forum
ARE WE READY TO TEACH YOUNG PEOPLE
to N O T repeat old stupidities, mistakes, or reinvent
something like wheels, hammers and so on ?
++regards
13. Code:
`middle = (low + high) / 2;`
"low + high" (before the divide-by-two is performed) can easily be bigger than an int. I think Nyan was indicating this.
14. I am having problems getting buggy output. Any chance you can supply some sample data that triggers the bug or is that giving too much away?
15. No Profile Picture
Closet coder
Devshed Beginner (1000 - 1499 posts)

Join Date
Feb 2005
Location
Plantation, FL <---south florida
Posts
1,431
Rep Power
153
does low and high represent the the lowest and highest values in the array?

so something like this would fail
Code:
```   int test_array[] = { 2, 5 };
printf( "bool = %d", binary_search(test_array, 5, 2, 5));```
since middle in binary_search is finding the average between the values themselves and not the average of the array size? (2 elements, but we try to access array[3] for the comparison)
Page 1 of 2 12 Last