# Binary search question

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.

• 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? – Kareem 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

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.

• 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`. – Kareem Sep 15 '14 at 13:33