Forums: » Register « |  Free Tools |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

New Free Tools on Dev Shed!

#1
December 8th, 2009, 07:55 PM
 Scorpions4ever
Banned ;)

Join Date: Nov 2001
Location: Woodland Hills, Los Angeles County, California, USA
Posts: 9,539
Time spent in forums: 2 Months 3 Days 9 h 15 m
Reputation Power: 4106
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.
__________________
Up the Irons
What Would Jimi Do? Smash amps. Burn guitar. Take the groupies home.
"Death Before Dishonour, my Friends!!" - Bruce D ickinson, Iron Maiden Aug 20, 2005 @ OzzFest
Down with Sharon Osbourne

Last edited by Scorpions4ever : December 8th, 2009 at 08:08 PM.

#2
December 8th, 2009, 08:20 PM
 mitakeet
I'm Baaaaaaack!

Join Date: Jul 2003
Location: Maryland
Posts: 5,538
Time spent in forums: 2 Weeks 4 Days 2 h 38 m 46 sec
Reputation Power: 243
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.
__________________

My blog, The Fount of Useless Information http://sol-biotech.com/wordpress/
Free code: http://sol-biotech.com/code/.
Secure Programming: http://sol-biotech.com/code/SecProgFAQ.html.
Performance Programming: http://sol-biotech.com/code/PerformanceProgramming.html.

It is not that old programmers are any smarter or code better, it is just that they have made the same stupid mistake so many times that it is second nature to fix it.
--Me, I just made it up

The reasonable man adapts himself to the world; the unreasonable one persists in trying to adapt the world to himself. Therefore, all progress depends on the unreasonable man.
--George Bernard Shaw

#3
December 8th, 2009, 10:38 PM
 Scorpions4ever
Banned ;)

Join Date: Nov 2001
Location: Woodland Hills, Los Angeles County, California, USA
Posts: 9,539
Time spent in forums: 2 Months 3 Days 9 h 15 m
Reputation Power: 4106
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 01:11 PM.

#4
December 8th, 2009, 10:53 PM
 lackoblacko
Registered User

Join Date: Dec 2009
Posts: 16
Time spent in forums: 16 h 40 m 25 sec
Reputation 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
December 8th, 2009, 11:43 PM
 Nyan
Contributing User

Join Date: Jan 2009
Posts: 337
Time spent in forums: 5 Days 2 h 15 m 47 sec
Reputation Power: 45
Is it overflow of (low + high)???

#6
December 9th, 2009, 02:57 AM
 jwdonahue
Contributing User

Join Date: May 2004
Posts: 3,417
Time spent in forums: 3 Weeks 5 Days 12 h 51 m 9 sec
Reputation Power: 886
Quote:
 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.

__________________
I no longer wish to be associated with this site.

Last edited by jwdonahue : December 9th, 2009 at 12:34 PM.

#7
December 9th, 2009, 02:59 AM
 jwdonahue
Contributing User

Join Date: May 2004
Posts: 3,417
Time spent in forums: 3 Weeks 5 Days 12 h 51 m 9 sec
Reputation Power: 886
Quote:
 Originally Posted by Scorpions4ever Usual puzzle of the week rules apply

Where can we find those?

#8
December 9th, 2009, 04:11 AM
 Nyan
Contributing User

Join Date: Jan 2009
Posts: 337
Time spent in forums: 5 Days 2 h 15 m 47 sec
Reputation Power: 45
ptr = (void*)((int*)array + middle * elem_size);

Shouldn't it be
(char*) array + middle * elem_size
??

#9
December 9th, 2009, 04:26 AM
 jwdonahue
Contributing User

Join Date: May 2004
Posts: 3,417
Time spent in forums: 3 Weeks 5 Days 12 h 51 m 9 sec
Reputation Power: 886
Quote:
 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
December 9th, 2009, 06:25 AM
 sizablegrin

Join Date: Jun 2005
Posts: 5,964
Time spent in forums: 2 Months 3 Weeks 2 Days 12 h 47 m 19 sec
Warnings Level: 10
Number of bans: 1
Reputation Power: 4851
JW, how come you quoted me in post #6? Scorp and I are not the same person.
__________________
Write no code whose complexity leaves you wondering what the hell you did.
Politically Incorrect DaWei on Pointers Grumpy on Exceptions

#11
December 9th, 2009, 07:26 AM
 guggach
Contributing User

Join Date: Jul 2004
Location: Middle Europa
Posts: 1,200
Time spent in forums: 1 Week 1 Day 11 h 47 m 52 sec
Reputation Power: 13
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!
__________________
working on Solaris[5-9], preferred languages french and C.

#12
December 9th, 2009, 07:33 AM
 guggach
Contributing User

Join Date: Jul 2004
Location: Middle Europa
Posts: 1,200
Time spent in forums: 1 Week 1 Day 11 h 47 m 52 sec
Reputation Power: 13
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
December 9th, 2009, 08:23 AM
 mike65535
um, Hello?

Join Date: Nov 2004
Location: FN23fc
Posts: 719
Time spent in forums: 1 Week 5 Days 1 h 42 m 56 sec
Reputation Power: 160
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.
__________________
"America's abundance was created not by public sacrifices to "the common good," but by the productive genius
of free men who pursued their own personal interests and the making of their own private fortunes. They did not
starve the people to pay for America's industrialization. They gave the people better jobs, higher wages and
cheaper goods with every new machine they invented, with every scientific discovery or technological advance --
and thus the whole country was moving forward and profiting, not suffering, every step of the way."
--Ayn Rand

#14
December 9th, 2009, 09:23 AM
 mitakeet
I'm Baaaaaaack!

Join Date: Jul 2003
Location: Maryland
Posts: 5,538
Time spent in forums: 2 Weeks 4 Days 2 h 38 m 46 sec
Reputation Power: 243
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
December 9th, 2009, 10:58 AM
 nattylife
Closet coder

Join Date: Feb 2005
Location: Plantation, FL <---south florida
Posts: 1,431
Time spent in forums: 2 Weeks 3 Days 13 h 33 m 57 sec
Reputation Power: 152
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)
__________________

 Viewing: Dev Shed Forums > Programming Languages > C Programming > C Puzzle of the week/month/year (2009-12-08)