0

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

Improve this question
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. ;-)

Improve this answer
  • Dude, I literally added an n--; line at the end of my while loop and it fixed it. :P YOU ARE A GENIUS! – Anza Khan Jun 6 '17 at 8:26
  • Well, it works, but how efficient is it? If there were millions of elements in the list, how long will it take to determine the needle isn't in the list? It becomes no more efficient than a linear search, defeating the purpose of the binary search.(If you were taking the on campus class, this method would lose a lot of points in the grade.) Most of the time, the while loop checks the relationship between min and max. Try printing out the values of min, mid and max inside the loop and run with the needle not in the list and watch what happens. It'll be very enlightening. – Cliff B Jun 6 '17 at 18:04
1

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.

Improve this answer
  • Thank you! I literally added a line that decrements the value of n (i.e n--; ) and it seemed to fix it!! – Anza Khan Jun 6 '17 at 8:27
  • "Seemed" to fix it is a good description. See my comment above. – Cliff B Jun 6 '17 at 18:05
  • @CliffB is 100% correct, this approach fixes the problem but is not efficient if you have a large array (the increment/decrement approach will consume time/resources). As he suggests, you will have to find a way to determine when you've exhausted the list (i.e. the binary search algorithm ceases to "work"). – ronga Jun 7 '17 at 9:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .