1

my binarysearch source code

I have tested the code presented in the picture and find this function always returns false no matter what number you search.There must be a problem in it but I can not see it!! Can anyone help me ? Thanks.

19

This is an example of a recursive call. Even though it is calling itself correctly, it is missing the code necessary to recursively return the result. As it is written above, it will execute the recursive call to itself, but when it does find a number, it will return true on the first step back through the recursion. However, at the second step and thereafter, the code will return to the calling recursion and process the next line of code because it has no instruction to do something else. It will drop through the if(min<max) block and hit the return false statement. So, from there on, it will just return false back up the recursion.

There is one condition where it will work. If the number of elements in array is odd and the middle element is sought, OR if even and the first element after the midpoint is sought, it will return true because it will hit on the first call and there are no recursive calls. You can prove this by testing.

The addition of one keyword, return, in two places, fixes the code:

    else if (key < array[middle])
         return BinarySearch(key, array, min, middle-1);
    else if (key > array[middle])
         return BinarySearch(key, array, middle+1, max); 

The code has to return the result of each call to BinarySearch to the calling code, whether it is to BinarySearch itself, or to main (or another calling function). Otherwise, it will just continue processing whatever comes next in the function.

If you're happy with this answer, please mark this question as answered. Let's keep up on forum housekeeping. ;-)

  • I can't thank you more for this wonderful answer. It really helps me get out of the confusion. – Yan Zhang May 10 '15 at 1:52
  • I want to thank you from the core of my heart. I thought I would never get out of this. – Mustaghees Aug 2 '15 at 8:23
  • 1
    You are a gentleman || lady and a scholar. I have been searching for two days, trying so many ways of hacking it together. Thank you so much. – AMadinger Oct 15 '15 at 6:06
  • Simply adding 2 returns and it worked! I'm so grateful, thank you very much! – user11052 Mar 10 '16 at 7:08
  • thanks a lot for this ! I have been trying to debug this from ages. I just can't thank you enough ! – user11691 Jun 16 '16 at 22:04
4

There was a question about this question on facebook, so instead of replying there, I thought I'd try to give some examples here, to supplement Cliff's amazing answer. It might be that none of this makes sense, but it's how I wrap my mind around it. Feel free to correct as necessary.


Let's work off the simplest case, an array of {1, 2, 3}.

If we are looking for 2, when we call BinarySearch(), it sees that the middle element matches 2 and it returns true.

If we search for 1, when we call BinarySearch(), it finds out 1 is less than the middle, and it calls a second BinarySearch() to search the left half of the array, which is just {1}.

This is where things get tricky.

First we need to recognize that the first BinarySearch() function is paused. It's just hanging out, waiting, while the second one runs.

So now the second BinarySearch() sees that the middle element matches 1 and it returns true. But what exactly does it mean that it "returns true"?

One way to visualize a function returning is to look back at the process that called it, replacing the function call with value that has been returned. Here's a small example:

int main(void)
{
    int i;
    i = GetInt();
    printf("%d",i);
}

If GetInt() returns 4, for example, we can think of it like this:

int main(void)
{
    int i;
    i = 4; // <---------------------------Substitute
    printf("%d",i);
}

So if we try this exercise with the code in BinarySearch(), it looks like this:

if (min <= max)
{
    int middle = (max-min) / 2 + min;
    if (key == array[middle])
        return true;
    else if (key < array[middle])
        BinarySearch(key, array, min, middle - 1);
    else if (key > array[middle])
        BinarySearch(key, array, middle + 1, max);
}
return false;

Now in our example above (looking for 1), the second BinarySearch() returned true, so let's make that substitution:

if (min <= max)
{
    int middle = (max-min) / 2 + min;
    if (key == array[middle])
        return true;
    else if (key < array[middle])
        true; // <---------------------------Substitute
    else if (key > array[middle])
        BinarySearch(key, array, middle + 1, max);
}
return false;

You can hopefully see that while the first BinarySearch() called the second BinarySearch(), and the second BinarySearch() returned true, the first BinarySearch() doesn't use "true" in any meaningful way...In fact, the first BinarySearch() will just continue operating, skipping over the next else if() and eventually returning false.

    else if (key > array[middle])
        BinarySearch(key, array, middle + 1, max);
}
return false;

In case it's still not clear, let's return to our GetInt() example above. It's as if we ignored the result of GetInt():

int main(void)
{
    int i;
    GetInt();
    printf("%d",i);
}

This will compile and run, and will just print whatever garbage happened to be in the memory the computer set aside for i.

If we try to compile:

int main(void)
{
    int i;
    4; // <---------------------------Substitute
    printf("%d",i);
}

The compiler is smart enough to recognize that something is fishy and it throws:

dumb.c:10:2: error: expression result unused [-Werror,-Wunused-value]
        4;
        ^
1 error generated.

So why doesn't it throw an error when we don't use the function's return value?

There are a lot of functions that are useful, but who return values we don't always care about. A good example is printf(), which actually returns an int. According to the man page,

Return value
Upon successful return, these functions return the number of characters printed (excluding the null byte used to end output to strings).

But we hardly ever use the return value.

So it all boils down to the fact that it isn't enough for each layer of binarysearch to call another search on a smaller array, it has to report back the result of the lower layers of the search.

  • thanks so much, i sort of understood cliff's answer, but just needed some clarity. you post made it completely clear what the issue was – user13597 Sep 7 '16 at 10:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .