Pset 3 Search what am i suppose to do?

Question

I have just started Pset3. I was going well until as per specification I read this

Re-write search in such a way that it uses linear search, returning true if value is in values and false if value is not in values. Take care to return false right away if n isn’t even positive.

I was like what am I suppose to do now? Still having no idea what to do I wrote this code in search function in helpers.c

bool search(int value, int values[], int n)
{
    if (n < 0)
    {
        return false;
    }
    for (int i = 0 ; i < n; i++)
    {
        if (values[i] == value)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
}

But didn't get the needle, so the question here is what am I supposed to do here? Am i going in the right direction? Any help or hint would really be appreciated.

Answer 1

First of all, the code you have written, is supposed to implement a linear search O(n), which means it traverses the whole values array and if it finds the value in there, it returns true, otherwise it returns false if the whole array has been traversed and value wasn't found. Your program doesn't work because of the

else
    return false;

clause. You should return false, only if if the whole array has been traversed and value wasn't found. You effectively check only the first item in values, and if it's equal to value you return true else you return false. You don't check any other items of the values array.

Apart from that, the binary search O(log(n)) uses a sorted array and in every iteration "cuts" the values to be searched in half, making it faster that linear search. If you watched the lectures you should know that.

To learn more about both searches, re-watch the lectures and read the articles in Wikipedia.

Linear search: https://en.wikipedia.org/wiki/Linear_search#Forward_iteration

Binary search: https://en.wikipedia.org/wiki/Binary_search_algorithm#Algorithm