0

I'm currently struggling with the binary search in pset 3 and I think I already found out how to implement it. I just really can't understand why, after return res;, the program does not leave the bysearch function.

When I run gdb using, for example, the value 4 and the haystack: 1, 2, 3, 4, 5, 6, 7, 8, 9; when it reaches the line "return res", instead of exiting the function, the program calls the bysearch function again using other values of min and max.

int bysearch(int value, int values[],int min,int max)
{
    int res = 0;
    int midpoint;

    if(max < min)
    {
        res = 0;
    }
    else
    {
        midpoint = findmid(min, max);

        if(values[midpoint] < value)
        {
            bysearch(value, values, midpoint+1, max);
        }
        else if(values[midpoint] > value)
        {
            bysearch(value, values, mid, midpoint-1);
        }
        else
        {
            res = 1;
        }
    }
    return res;
}

This is what happens, gdb. enter image description here

9
  • 1
    How do you know the function isn't returning? Is there a reason your function returns an int rather than a bool? – curiouskiwi Sep 9 '14 at 1:29
  • last 47? what does it mean? – sinister Sep 9 '14 at 2:34
  • Also, how does your findmid() function work? What's the formula for finding the middle index? – kzidane Sep 9 '14 at 3:06
  • @curiouskiwi you're right, my fault on the int rather than the bool – user1782 Sep 9 '14 at 10:18
  • *line 47 @sinister – user1782 Sep 9 '14 at 10:18
0

Well, I don't know what line 47 is exactly since there is no line numbering here, but I assume it's one of the recursive calls in this function, specifically, the one that's executed when values[midpoint] > value and that sounds normal since the minimum index is initially 0, the maximum index is initially 8 and the midpoint is (0 + 8) / 2 which is 4. values[4] is equal to 5 and that's why the function is called again!

In fact, it should keep getting called until midpoint is equal to 3. So,

the first call:

min = 0 // initial min
max = 8 // initial max
midpoint = (0 + 8) / 2 = 4

values[4] = 5 // not what we're looking for

the second call:

min = 0
max = 3 // mid - 1
midpoint = (0 + 3) / 2 = 1 // integer division

values[1] = 2 // not what we're looking for

the third call:

min = 2 // mid + 1
max = 3
midpoint = (2 + 3) / 2 // integer division

values[2] = 3 // still not what we're looking for

the fourth call:

min = 3 // mid + 1
max = 3 
mid = (3 + 3) / 2 = 3

values[3] = 4 // gotcha

as you can see, it should take you 4 calls to find the value 4.

3
  • the functions does exactly what you told and it takes me 4 calls to find the value 4. The problem is that the function doesn't return right after and calls again the bysearch function. I'll send a PRTSC of GDB for you to see – user1782 Sep 15 '14 at 0:53
  • do you think you can take a look? – user1782 Sep 15 '14 at 13:29
  • @user1782, well that's what you're telling it to do exactly if values[midpoint] is not greater than value nor less than it, you return 1 from the else statement — when values[midpoint] is equal to value. – kzidane Sep 15 '14 at 13:33

You must log in to answer this question.

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