Binary Search for helpers.c

Question

so as the title suggests I am having some trouble with my implementation of binary search. So based on the logic shown in the lecture, I think my implementation is fine, indeed it works for the cases where the value is inside the array, however the case where the value is not in the array, it hangs and says the value cannot be found. Sorting is fine, its just the case where the value is not in the array that it fails.

bool search(int value, int values[], int n)
{
// TODO: implement a searching algorithm
int max = n-1;
int min = 0;

if(n < 0)
{
    return false;
}

while(n > 0)
{
    int middle = ((max)+min)/2;

    if(values[middle]==value)
    {
        return true;
    }
    else if(values[middle]> value)
    {
       // middle = ((middle-1)+min)/2;
       max = middle - 1;
    }
    else if(values[middle] < value)
    {
        min = middle+1;
    }
}
return false;
}

THE OUTPUT:

:) helpers.c exists
:) helpers.c compiles
:) finds 42 in {42,43,44}
:) finds 42 in {41,42,43}
:) finds 42 in {40,41,42}
:) finds 42 in {41,42,43,44}
:) finds 42 in {40,41,42,43}
:) finds 42 in {39,40,41,42}
**:( doesn't find 42 in {39,40,41}
   \ killed by server
:( doesn't find 42 in {39,40,41,43}
   \ killed by server**
:) finds 42 in {42,40,39,41}

https://sandbox.cs50.net/checks/586c0fdc7e414d5ebced4f29e20c9c33

Answer 1

"killed by server" usually indicates an infinite loop, which is exactly what is happening here. Take a good look at your search function and consider what happens when a number is not in the list.

The search function will enter the while loop and will run while n>0. Since there's nothing in the while loop to alter the value of n, it will run until it hits a return statement. But the only way that happens is if the needle is actually in this haystack. If it isn't, it just runs forever.

Instead of a test for n > 1, there needs to be a test for a condition that indicates that the list has been exhausted. I'll leave it to you to chew on that one for a while. ;-)

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)

Answer 2

Your code will keep on running as long as n>0, and since n is static, it keeps on going even if the value is not in the array. A better way would be to keep track of how many times you've looked through the array and return false if you've looked more than n times.