0

My sort function is working correctly, but my binary search always fails to find value.

I think my logic for the search is solid: I compare the value I'm searching for to the value at the midpoint of the sorted array and if the value isn't at the midpoint, I restart the search on all values above(if the midpoint value is less than target value) or below the midpoint (if midpoint > value):

/**
 * Returns true if value is in array of n values, else false.
 */
 bool bin_search (int value, int values[], int a, int n)
{
    int mid = (n + a) / 2;
    int i = values[mid];

    // if a > n, the search is complete and value is not in the array     
    if (a > n || value > values[n] || value < values[a])
    {
        return false;
    }

    if (i == value)
    {
        return true;
    }        

    // if i < value search values greater than the midpoint
    else if (i < value)
    {   
        a = mid + 1;
        bin_search (value, values, a, n);
    }

    // if i > value search values less than the midpoint
    else if (i > value)
    {   
        n = mid - 1;
        bin_search (value, values, a, n);
    }

    return false;
}

bool search(int value, int values[], int n)
{
    // int a is the first element in the array values[] and is 0 by default
    int a = 0;    
    return bin_search (value, values, a, n);
}
0
0

This is almost a perfect duplicate of an earlier problem. Your search works fine and actually does find the target. It just doesn't have the correct return code. It will return from the recursive calls and drop through to the fina return false; every time. See discussion on duplicated question at

Pset3 Binary Search problems

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