0

I'm at the very end of the "find, sort, search" section of pset3, but when using check50, I get "expected an exit code of 0, not 1". This only happens on the checks where check50 is looking for a value. My code reports just fine that it doesn't find values check50 searches for on the last two checks. Here's the code for my binary search:

bool search(int value, int values[], int n)
{
    if (n <= 0)
        return false;
    else
    {    
        // TODO: implement a searching algorithm
        int min = values[0];
        int max = values[n-1];
        int mid = ((max + min) / 2);

        bool present = false;
        for(int i = 0; i < n-1; i++)
        {
            if(value == values [i])
            {
                present = true;
                break;
            }
        }
        if(present == true)
        {
            while(mid != value)
            {
                if(value > mid)
                {
                    min = mid;
                    mid = ((max + min) / 2);
                }
                else if(value < mid)
                {
                    max = mid;
                    mid = ((max + min) / 2);
                }
                else 
                {
                    return true;
                }
            }
        }
    }
    return false;
}

Any thoughts about what might be causing it? What am I missing?

Thanks in advance!

0

Very simply put, your search function never reports finding a number, even if it is there.

Your for loop does a linear search for the number in the list and will successfully find it if it is there, and will set present = true;.

Next, you then try to do a binary search with the while loop. Here's where it breaks. The while tests to see that value does not equal the target. If it's not, the loop executes another pass. Eventually, (assuming it's working correctly) one of the if statements will set mid to the target value and the code will skip past the remaining else clause(s) and go back to the top. At this point, the test detects that mid equals the target and the loop immediately ends BEFORE IT CAN PROCESS THE RETURN TRUE. In other words, return true will never happen. You need to rethink how that while loop is structured.

Now, here's my next question. As I recall, there were two parts to the assignment. One was to implement a linear search, which you did. The next part was to implement a binary search, replacing the linear search. To quote the assignment, "Rip out the lines that you wrote earlier (sniff) and re-implement search as Binary Search, that divide-and-conquer strategy that we employed in Week 0." Why are you doing both?

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

| improve this answer | |
  • Ah ha, ok, I see the problem. My code originally didn't report not finding a number, so that was what the bool and linear search was. At the time, though, I didn't realize it was REimplementing linear search. I see the mistake now. Thanks! – Chris Sep 29 '15 at 2:43

You must log in to answer this question.

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