I'm struggling with implementation of binary search in PSet 3, and my code can't quite get past check50.
Here's my code:
bool search(int value, int values[], int n)
{
// TODO: implement a searching algorithm
int min = 0; //initial minimum value
int max = n - 1; //initial maximum value
int midpoint = (max + min)/2; // calculation of midpoint value
while (min <= max) // search as long as there is at least 1 element in the array
{
//if the midpoint happens to be the number we're looking for
if (values[midpoint] == value) {
return true;
}
//if midpoint is less than the number we're looking for
else if (values[midpoint] < value) {
min = midpoint + 1;
}
//if the midpoint is more than the number we're looking for
else {
max = midpoint - 1;
}
//set the new length of the array
n = max - min + 1;
return true;
}
return false;
}
And here's what check50 gives me:
:( doesn't find 42 in {39,40,41} \ expected an exit code of 1, not 0 :( doesn't find 42 in {39,40,41,43} \ expected an exit code of 1, not 0
It seems that the problem is that my code doesn't return false when the value isn't in the array. I thought the problem was caused by the second return true, but when I remove it, check50 gives even worse results:
:) helpers.c exists :) helpers.c compiles :( finds 42 in {42,43,44} \ killed by server :) finds 42 in {41,42,43} :( finds 42 in {40,41,42} \ killed by server :) finds 42 in {41,42,43,44} :( finds 42 in {40,41,42,43} \ killed by server :( finds 42 in {39,40,41,42} \ killed by server :( doesn't find 42 in {39,40,41} \ killed by server :( doesn't find 42 in {39,40,41,43} \ killed by server
Any help is very much appreciated!:)