Pset3 helpers.c

Question

i'm stuck in binary search. Check50 doesn't pass all the checks and it doesn't find the needle, I feel like the algorithm i have implemented is correct but it doesn't work. I've been stuck in this for a while. Can anyone please have a look on this and help me out, thanks!

bool search(int value, int values[], int n)
{
   // TODO: implement a searching algorithm

int start,mid,end;

if(n < 0)
{
    return 1;
}

start = 0;
end = n - 1;

while(start < end)
{
    mid = values[(start+end)/2];

    if(value == mid)
    {
        return true;
    }
    if(value < mid)
    {
        end = mid - 1;
    }
    if(value > mid)
    {
        start = mid + 1;
    }
}
return false;


}

Answer 1

While start and end are just indexes, mid is a value from your array. So on the 1st iteration, start = 0, end = 3-1 = 2 and mid = values[1] = 43. As you wrote the code, mid is not the (start + end) / 2, it is the value indexed by (start + end) / 2 in your array!

Answer 2

No, it is not correct. let's look what happens when values[] = {42,43,44} that is n = 3, and value == 42.

After first iteration it sets mid = values[(start + end)/2] = values [1] = 43. Then, as value(42) less than mid(43) it sets end = mid -1 = 42.

On the second iteration it sets mid = values[(start + end)/2} = values [21] that is nonsense