# 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? Sep 9 '14 at 1:29
• last 47? what does it mean? 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 Sep 9 '14 at 10:18
• *line 47 @sinister 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 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 = 5 // not what we're looking for


the second call:

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

values = 2 // not what we're looking for


the third call:

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

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


the fourth call:

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

values = 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 Sep 15 '14 at 0:53
• do you think you can take a look? 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