cb3k cb3k - 8 days ago 6
C Question

If statement not recognizing true conditions?

I'm having trouble with this binary search algorithm. Here are explanations of the variables.

value: the number being searched within the array

values[]: the array that is being searched

n: number of elements in the array

high: highest element (by zero indexed position) of portion of the array being searched

low: lowest element (by zero indexed position) the portion of the array being searched

My problem isn't the recursion. The portion of the array being searched centers around "value" and conditions identified below are being met. the problem is that my if statements don't seem to be recognizing that they are. I know the conditions are being met because when I print out values[high], values[middle], and values[low] for each recursion it shows that they are.

int search(int value, int values[], int n, int high, int low)
{
if (n <= 0)
{
return 1;
}

int middle = (high + low) / 2;

///condition #1
if (value == values[middle])
{
return 0;
}

//conditions #2 and #3 (account for the maxes and mins of the array because the operation to find middle truncates)
else if ( values[middle]==values[low] || values[middle]==values[high])
{
return 0;
}

else if (value > values[middle])
{
low = middle;
search(value, values, n, high, low);
}

else if (value < values[middle])
{
high = middle;
search(value, values, n, high, low);
}

return 2;
}


What's wrong here?

Answer

Look closely at this code:

else if (value > values[middle])
{
     low = middle;
     search(value, values, n, high, low);
}

else if (value < values[middle])
{
   high = middle;
   search(value, values, n, high, low);
}

Notice that in these cases you call the search function recursively, but you don't do anything with the return value. This means that whatever value returned by search is discarded and the code continues on as usually, ultimately returning 2.

To fix this, add in these return statements:

else if (value > values[middle])
{
     low = middle;
     return search(value, values, n, high, low);
}

else if (value < values[middle])
{
   high = middle;
   return search(value, values, n, high, low);
}

Generally speaking, if you suspect that an if statement condition isn't firing, it's worth slowly stepping through things with a debugger. Doing so would likely lead you to notice that you were (1) calling the function recursively correctly but (2) returning and discarding the returned value.

There may be other issues with the code here, but this is certainly something that you're going to need to address.

Comments