0

I've been having some problems with the implementation of a Binary search algorithm. The problem is that it always returns false.

           else if(values[midpoint] == value) 
                    {
                       printf("==");
                       return true;
                    }

This part is redundant and just a return true would suffice, and the first "if(n<=m)" would know if the number is not the same, however, this too doesn't work.

Bottom line is: the returns are not working properly

The array is sorted and everything should have been working properly... still, it is my first time using recurring functions.

Can someone help? Thanks!

Here is what the code looks like:

bool search(int value, int values[], int n, int m)

{

if(n<=m)
{
    printf("n<=m");
    return false;
}



int midpoint = (m+n)/2;
printf("\nmidpoint %d max:%d min:%d, value: %d",midpoint, n, m, values[midpoint]);   


if (values[midpoint] > value)
    {
    printf("\n%d > %d",values[midpoint],value);
    n = midpoint-1;
    search(value, values, n, m);

    }

    else if (values[midpoint] < value)
        {
        printf("\n%d < %d",values[midpoint],value);
        m = midpoint+1;
        search(value, values, n, m);
        }
           else if(values[midpoint] == value)
                    {
                       printf("==");
                       return true;
                    }

            return false;
     }       
2
  • Can you explain what are 'm' and 'n' and the starting values you gave them. Btw i am not sure but i think you are not allowed to change the declaration of search for the pset3. – wallek876 Jan 12 '15 at 15:53
  • 'm' should be the minimum and 'n' the maximum. Oh, I see, you do have a point... Kareem made an answer that states that exactly. – CapsuleMaglev Jan 13 '15 at 12:54
1

From the pset specification page

You are welcome to take an iterative approach (as with a loop) or a recursive approach (wherein a function calls itself). If you pursue the latter, though, know that you may not change our declaration of search, but you may write a new, recursive function (that perhaps takes different parameters) that search itself calls.

As for your searching algorithms, here's a couple of points

  • assume 3 recursive calls were made to find value, if the last call returned true, what do you think the second and the first call would return?

  • you don't really have to write

    else if (values[midpoint] == value)
    {
        // do something
    }
    

    since writing

    else
    {
        // do something
    }
    

    would be sufficient in this case because obviously if values[midpoint] is not greater than nor less than value, then they are definitely equal to each others.

3
  • Absolutely! That's exactly what I meant by redundancy. Now that you said that the first and the second calls should return values as well, I am a bit confused. I thought that if you made a recursion, the first and the second calls would be "forgotten" and wouldn't need to return a value, isn't that the case? I mean... if this is a function, how will the compiler choose which call will return an actual value to the calling function? Thanks for your reply, Kareem! – CapsuleMaglev Jan 13 '15 at 12:58
  • @Zellator I think people often get confused about recursion at first. And no, that is not the case (at least in C). If the body of a function a called a function b, the value returned from b (if any) would be returned to a. If you want to hand this value back to the caller of a, you probably should return this value from a. Take your time reasoning about this and see what you can do with that in terms of a recursive function (which is obviously a function that calls itself). – Kareem Jan 13 '15 at 16:55
  • When you put it that way it makes a lot of sense. I understand what is going on now. Thanks for the help, I really appreciate it. :) – CapsuleMaglev Jan 14 '15 at 16:12

You must log in to answer this question.

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