3

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;
}
Improve this question
2
  • Where does the constraint of three parameters come from? Seems a bit arbitrary. Commented Oct 24, 2012 at 11:40
  • @Gracenotes At the time of writing this I didn't understand a lot of fundamentals about OOP. It is indeed arbitrary. Commented Jul 22, 2013 at 17:56

3 Answers 3

Reset to default
6

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);
    }
 }
Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Honestly I'm just practicing stuff out for internship interviews. The more I can avoid STL functions, the better. I guess the problem is pretty straight forward if I use four parameters, I was just curious if I could get it in three.
If you're using vector slicing, you can do it in 2 parameters. For core algorithms, though, there is nothing to be gained by golfing parameter counts.
You can do it with one parameter. Just stuff everything into a struct and pass that...
Very true. That way, bool serveWithScones doesn't need to be left out.
2

If you want to do it recursive, your method needs to take the search range as parameters. Else you can't keep track of where to search in the rucursive call assuming you always give the full vector to the function.

So your method signature should be like:

int recBSearch(vector<int> v, int first, int last, int item)
Improve this answer

6 Comments

That's not necessary. Parameter v for each recursive call doesn't have to be constant thus can mark the beginning of the range. And size can be used to deduce the end of the range.
but copying the vector is actually an error if you want something "optimal" as marked in the tags.
@Tobias Langner that's what references and pointers for... You don't have to pass the vector by value.
You would have to produce a new vector though, but the index returned would be of that vector not of the original one. so if you are not at the start of the range, you wouldn't know what to add to the offset if found. If it returned bool you could do that, but the function is supposed to return the index if found else return -1.
@CashCow Good point. This can be addressed by doing something like return index + recBSearch(v, size, item). Anyway, my point was that it's doable with the proposed function signature (there are probably some more errors in the original code).
|
0

Binary search basically works by dividing your range in 2 halves and searching in each one of them. Your code shows that you operate on the lower half for your both branches. You need to pass to the recursive call the higher half of your v vector in the second else if as well as size/2 instead of size.

Improve this answer

1 Comment

Thanks, much. I knew I would feel like an idiot reading the response I'd get, but thanks nonetheless! Just a college student trying to learn stuff in the middle of the night.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.