0

Why does my code fail check50?

This is the code of my binary search. I know it's buggy, and I spent the last hours reading answers to similar questions, the information I found doesn't quite cut it and I can't put my finger on what I'm doing wrong.

bool search (int value, int values[], int n)
}
    int first = 0;
    int last = n - 1;
    int middle = (first+last)/2;

    while (first <= last) 
    {
        if (values[middle] > value)
        {
            first = middle + 1;
        }
        else if (values[middle] == value) 
        {
            return true;
        }
        else
        {
            last = middle - 1;
        }
        middle = (first + last)/2;
    }
}

The output of check50 is this:

:) helpers.c exists

:) helpers.c compiles

:( finds 42 in {42,43,44}
   \ expected an exit code of 0, not 1

:) finds 42 in {41,42,43}

:( finds 42 in {40,41,42}
   \ expected an exit code of 0, not 1

:) finds 42 in {41,42,43,44}

:( finds 42 in {40,41,42,43}
   \ expected an exit code of 0, not 1

:( finds 42 in {39,40,41,42}
   \ expected an exit code of 0, not 1

:) doesn't find 42 in {39,40,41}

:) doesn't find 42 in {39,40,41,43}

https://sandbox.cs50.net/checks/44905bf09eed41bd99d0df993e43f55a

I don't really care if you mark this question as a "duplicate", I've searched this forum for literally hours to no avail, so, it's not a duplicate for me. All the answers I found are too cryptic. Any help is appreciated.

2

The reason that the other questions aren't helping is that you've come up with a problem that appears to be unique. Take a look at the following code, particularly the test condition:

    if (values[middle] > value)
    {
        first = middle + 1;
    }

If the test condition is true, that means that the target is in the lower half of the list, but the code then narrows the search to the top half. Does that seem right? ;-)

The same effect happens if the target is in the top half. The code will then search the bottom half, where the target cannot possibly be. The only tests that pass happen when the target is equal to the middle value.

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

1
  • Hey Cliff B, as usual, great insight. You've been extremely helpful. I only needed to correct the if statements to have the loop search in the correct half of the array on each iteration. Jul 25 '16 at 21:46
0

(this answer previously stated that the code went into an infinite loop but has been since corrected after Cliff B pointed out my error. Thanks for the feedback, Cliff!)

Have you tried running your program with the values check50 is using?

Looking at the first set of values (42,43,44), your code exits when it shouldn't. Perhaps the same is happening in the other cases?

For example, when values[2] = {42,43,44}

First iteration:

value = 42
values[0] = 42
values[1] = 43
values[2] = 44
n = 3
first = 0
last = n - 1 = 2
middle = (first + last)/2 = (0 + 2)/2 = 2/2 = 1

0 is smaller than 2, so if(first <= last) is true

values[1] (43) is larger than 42, so if (values[middle] > value) is true. Thus:

first = middle + 1 = 1 + 1 = 2

Note that your search is moving towards the upper half of the array (as of now, your middle element is values[2]) but, 42 is not in this half!

As Cliff points out, should you be checking whether the sought value is smaller than the middle element if you will then be converting that middle element into the first element of your new search?

If your program continues, eventually first goes up to 3, (first <= last) is false, and search exits --incorrectly-- returning a "not found" signal. (--CORRECTED-- thanks, @Cliff_B, for your suggestions to improve this answer!)

Hope this helps!

4
  • 1
    Interesting analysis, but incorrect. There is no infinite loop. At the start of the third iteration, as you said, first = 3, last = 2, an the test condition is while (first <= last) . Since first is greater than last, or 3>2, the test fails and the loop exits. Also, if there were an infinite loop, the program would have to be manually terminated and/or check50 would time out and generate a totally different error.
    – Cliff B
    Jul 25 '16 at 2:48
  • Oh, gee. Worst thing is that that's what I first thought but then substituted the incorrect value and then followed the wrong path :/ Thanks for pointing this error out, and apologies for adding to the workload
    – dmorali
    Jul 25 '16 at 3:38
  • Not a problem. Everyone makes mistakes sooner or later. But that's where we all learn the best lessons. ;-)
    – Cliff B
    Jul 25 '16 at 4:00
  • 1
    Now, the analysis is correct, and useful for understanding how things work, but after the first iteration, it's unnecessary. As you demonstrated, the target is in the lower half of the sorted list, but the search is looking in the top half after the first iteration, clearly a problem. The key question is why does this happen? SPOILER ALERT! - the whole problem can be fixed by changing one single character in the code. ;->
    – Cliff B
    Jul 25 '16 at 5:32

You must log in to answer this question.

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