C++ Recursive Binary Search with Three Parameters

Question

I'm 99% sure my problem is that I'm setting low to zero every start. But I'm not sure how to keep low consistently representative of the low index regardless of the depth of my recursion. If it accurately told me the index of the low index I don't think I would have a problem.

Here's my code so far:

int recBSearch(vector<int> v, int size, int item)
{
    int index = size / 2;
    int curr = v[index];
    int low = 0;
    int high = size -1;
    if (v[index] == item)
        return index;
    else if (v[index] > item)
    {
        high = index;
        index = (high+low)/2;
        size = high - low;
        return recBSearch(v, size, item);
    }
    else if (v[index] < item)
    {
        low = index;
        index = (high+low)/2;
        size = high - low;
        return recBSearch(v, size, item);
    }
    return -1;
}

Answer 1

This won't work when you are trying to search in the upper half of the vector, because what you really need to create is a slice of the vector.

There is already a binary search but if you are determined to write your own, use an iterator-range in the parameters. (You can either pass in two plain iterators or a boost range).

You want -1 if not found else the iterator location, so in your slice (iterator range) you would need to specify a starting index number in case it is found.

You could also pass, as an alternative, the vector (by const reference) and the range in which you wish to search.

Your last line is unreachable. Instead it should be the terminating condition of your recursion before you do any evaluation. (If your range is empty)

The version that would iterate by passing by reference and using index numbers (simplest) would look like this:

int recBSearch( std::vector<int> const& vec, int start, int end, int value )
{
    if( start == end )
    {
       return -1;
    }
    int index = (start + end) / 2;
    // continue from here
}

end would indicate "one past the last element" so if the vector has size 5, the first iteration would pass 0 and 5. If the vector is empty, you pass 0 and 0.

As an exercise, "can it be done with 3 parameters"?

Yes...

 typedef std::vector<int>::const_iterator citer;
 int recBSearch( citer start, citer end, int value )
 {
    if( start == end )
    {
       return -1;
    }
    citer middle = start + (end-start)/2;
    if( *value == *middle )
    {
       return middle - start;
    }
    else if ( *value < *middle )
    {
       return recBSearch( start, middle, value );
    }
    else // note the change here
    {
        int res = recBSearch( middle+1, end, value );
        if( res == -1 )
           return -1;
        else
           return res + 1 + (middle-start);
    }
 }