Binary search question

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.

Answer 1

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.