0

I've been stuck with this particular problem for a while and can't think of what goes wrong. So any help will be much appreciated :) Binary search seems to work with all cases except when the searched element is the first one (for instance, if we look for 28 and input an array of 3 elements [28, 29, 30]). When we are through the first loop in value < values[middle] condition, we call the function recursively with an array size of one and should end up in condition value == values[middle], but it doesn't really happen.

bool search(int value, int values[], int n)
{
    if (n < 2)
    {
        if (value == values[0])
        {
            return true;
        }
        else
        {
            return false;
        }
    } 
    int middle = n/2;
    int NewArray[middle]; 
    if (value == values[middle])
    {
       return true;
    }
    else if (value > values[middle])
    {
        int NewSize = n - middle - 1;
        for (int i = 0, j = middle+1; i < NewSize; i++, j++)
        {
            NewArray[i] = values[j];
        }
        return search(value, NewArray, NewSize);
    }
    else if (value < values[middle])
    {
        int NewSize = n - middle;
        for (int i = 0, j = 0; i < middle; i++, j++)
        {
            NewArray[i] = values[j];
        }
        return search(value, NewArray, NewSize);
    }
    else 
    {
        return false;
    }
}
1

Use int NewSize = middle;, not = n - middle;, in the value < values[middle] part.

Also,

    if (n < 2)
    {
        if (value == values[0])
        {
            return true;
        }
        else
        {
            return false;
        }
    } 

could be just

    if (n < 1)
    {
        return false;
    }

And if you want, there's some fun with arrays:

        return search(value, &values[middle + 1], NewSize);

and

        return search(value, values, NewSize);

work without copying :)

1
  • thanks so much for your help! everything works now :) – Ksenia Klokova Oct 23 '17 at 20:15

You must log in to answer this question.

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