If statement not recognizing true conditions?

Question

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?

I took a very brief look at your problem but usually when I see I problem like this it is related to this http://stackoverflow.com/questions/9529422/difference-between-operator-and-equals-method-in-c — knowads, Jul 19 '16 at 21:35
Can you expand your example to be complete and show the incorrect behavior? — Retired Ninja, Jul 19 '16 at 21:36
I think you should compare `middle` to `high` and `low` rather than `values[]` with these indices... — Eugene Sh., Jul 19 '16 at 21:36

score 3 · Accepted Answer · answered Jul 19 '16 at 21:37

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.

I think there are multiple other problems with the code, but this is one of the problems. — Jonathan Leffler, Jul 19 '16 at 21:43
that seemed to make it work... what might the other problems be? The array is sorted already. — cb3k, Jul 19 '16 at 21:48

score 2 · Answer 2 · edited May 23 '17 at 12:24

Quoth cb3k

That seemed to make it work...what might the other problems be?

Here's your code with the minimal (necessary, but not sufficient) fix diagnosed by templatetypedef and a test harness.

#include <stdio.h>

static
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;
        return search(value, values, n, high, low);
    }

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

    return 2;
}

int main(void)
{
    int data[15];
    for (int i = 0; i < 15; i++)
        data[i] = 2 * i + 1;

    printf("Data:");
    for (int i = 0; i < 15; i++)
        printf("%3d", data[i]);
    putchar('\n');

    for (int i = -1; i < 2 * 15 + 3; i++)
        printf("Search for %2d - result %d\n", i, search(i, data, 15, 14, 0));
    return 0;
}

Here's the output:

Data:  1  3  5  7  9 11 13 15 17 19 21 23 25 27 29
Search for -1 - result 0
Search for  0 - result 0
Search for  1 - result 0
Search for  2 - result 0
Search for  3 - result 0
Search for  4 - result 0
Search for  5 - result 0
Search for  6 - result 0
Search for  7 - result 0
Search for  8 - result 0
Search for  9 - result 0
Search for 10 - result 0
Search for 11 - result 0
Search for 12 - result 0
Search for 13 - result 0
Search for 14 - result 0
Search for 15 - result 0
Search for 16 - result 0
Search for 17 - result 0
Search for 18 - result 0
Search for 19 - result 0
Search for 20 - result 0
Search for 21 - result 0
Search for 22 - result 0
Search for 23 - result 0
Search for 24 - result 0
Search for 25 - result 0
Search for 26 - result 0
Search for 27 - result 0
Search for 28 - result 0
Search for 29 - result 0
Search for 30 - result 0
Search for 31 - result 0
Search for 32 - result 0

It is returning 0 regardless of whether the value sought is present in the array or not. This is incorrect behaviour.

You should take time out to study Programming Pearls by Jon Bentley. It covers a lot the basics of the testing of binary searches in a variety of forms — the test harness shown is a variant on what he describes. Also take the time to read Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken. Maybe you should take reassurance that lots of other people have got binary search wrong over time. (IIRC, the first versions of binary search were published in the 1950s, but it wasn't until the early 1960s that a correct version was published — and then there's the Extra information from 2006, too.)

When I added a printf() in the block after else if (values[middle] == values[low] || values[middle] == values[high]), it printed on every search that should have failed. Note that the interface makes it hard to spot what's happening — it doesn't report where the element is found, just whether it is found. You can add the debugging and code changes necessary to deal with the residual problems. (Hint: that condition is probably not part of the solution. However, when you do remove it, the code goes into a permanent loop because you don't eliminate the value known not to be in the range from the range that you check recursively.)

This seems to work — note that return 2; is never executed (because the final else if is never false.

#include <stdio.h>

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

    int middle = (high + low) / 2;

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

#if 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])
    {
        //printf(" (#2 || #3) ");
        return 0;
    }
#endif

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

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

    return 2;
}

int main(void)
{
    int data[15];
    for (int i = 0; i < 15; i++)
        data[i] = 2 * i + 1;

    printf("Data:");
    for (int i = 0; i < 15; i++)
        printf("%3d", data[i]);
    putchar('\n');

    for (int i = -1; i < 2 * 15 + 3; i++)
        printf("Search for %2d - result %d\n", i, search(i, data, 15, 14, 0));
    return 0;
}

Output:

Data:  1  3  5  7  9 11 13 15 17 19 21 23 25 27 29
Search for -1 - result 1
Search for  0 - result 1
Search for  1 - result 0
Search for  2 - result 1
Search for  3 - result 0
Search for  4 - result 1
Search for  5 - result 0
Search for  6 - result 1
Search for  7 - result 0
Search for  8 - result 1
Search for  9 - result 0
Search for 10 - result 1
Search for 11 - result 0
Search for 12 - result 1
Search for 13 - result 0
Search for 14 - result 1
Search for 15 - result 0
Search for 16 - result 1
Search for 17 - result 0
Search for 18 - result 1
Search for 19 - result 0
Search for 20 - result 1
Search for 21 - result 0
Search for 22 - result 1
Search for 23 - result 0
Search for 24 - result 1
Search for 25 - result 0
Search for 26 - result 1
Search for 27 - result 0
Search for 28 - result 1
Search for 29 - result 0
Search for 30 - result 1
Search for 31 - result 1
Search for 32 - result 1

If statement not recognizing true conditions?

2 Answers2

Linked