Pset 3 - Find and Helper.C

Question

Question about find and helpers.c. When I run check50 on my code, I get the following error below:

:( doesn't find 42 in {39,40,41} \ expected an exit code of 1, not 0

:( doesn't find 42 in {39,40,41,43} \ expected an exit code of 1, not 0

I know that I should be returning 1 because 42 is indeed not in the list of numbers and I believe this relates to my binary search portion of my code but I can't figure out why it won't work. Any insight would be much appreciated. I did not modify find.c at all.

Here is the binary search algorithm I'm using:

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

Answer 1

You are comparing min and max. You should be comparing values[min] and values[max]

Otherwise, you end up with, for example:

 {41,42,43} so n = 3

 min is 0, max is 2

 mid is 1.

 if 1 == 42
 else if 1 < 42
     min = 1

etc. when you should be doing

 if values[1] == 42    (and values[1] is 42)

Also, as Paul said in his answer, remove that extraneous return true.

Answer 2

The problem is in you while loop. There is an extraneous return true; statement at the bottom of the loop which causes it to return true after the first iteration regardless of whether or not the value has been found. The line that should be removed is shown below.

>     while (max >= min)
>     {
>     int mid = (max+min)/2;
>         if (mid == value)
>         {
>             return true;
>         }
>         else if (mid < value)
>         {
>         min = mid+1;
>         }
>         else if (mid > value)
>         {
>         max = mid-1;
>         }
>        **return true; <- remove this line**
>     }