Linear recursive search c++

Asked

Viewed 540 times

3

I wanted to do a recursive linear search using vector and iterators, here’s the code:

long int busca_sr(std::vector<long int> &amostra, const long int &key){
    auto first = amostra.begin();
    auto last = amostra.end();
    if (last == first-1){
        return -1;
    }
    else if(*last == key){
        return 1;
    }
    else{ 
        --last;
        std::vector <long int> auxi1 (first, last);
        return busca_sr(auxi1, key); 

    }

The problem is that when I run this function my pc hangs, I suspect that the error is in the stopping condition of my recursion, because when the last is equal to the first the auxiliary vector down there will not be allocated, wanted a way to insert a stop condition without having to change the function signature!

c++
  • 1

    You should not dereference the value of end(), which occurs in *last == key. source: http://www.cplusplus.com/reference/vector/vector/end/

1 answer

0

Since it’s a linear search, I think it’s more natural for you to start the check from the first element and advance the start iterator by 1 instead of starting with the last element.

Another point that was wrong was the stopping criterion: the condition if(last == first-1) always gives exception, because you are trying to read an index before the first position. To find out if the iterator arrived at the end of the vector, just check v.begin() == v.end().

long int busca_sr(std::vector<long int> &amostra, const long int &key) {
    std::vector<long int>::iterator first = amostra.begin();
    std::vector<long int>::iterator last = amostra.end();

    if (last == first) {
        return -1;
    }
    else if (*first == key) {
        return 1;
    }
    else {
        std::vector <long int> auxi1(++first, last);
        return busca_sr(auxi1, key);
    }
}

Browser other questions tagged c++

You are not signed in. Login or sign up in order to post.