Recursive linear search c ++

Question

Recursive linear search c ++

Navigation

#1 by (0 votes)

1

I have a problem here, 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 the error is in the stop condition of my recursion, because when last is equal to first the auxiliary vector la will not be allocated, wanted a way to enter a stop condition without having to change the signature of the function, thanks!

c++

asked by anonymous 19.03.2017 / 18:21

1 answer

Jpa does not create column @lob Error LNK2019 compiling OpenCL Project on Windows [closed]

score 0 · Answer 1

Since it's a linear search, I think it's more natural for you to start checking from the first element and to move the iterator forward from the beginning to 1 instead of starting with the last element.

Another point that was wrong was the stop criterion: if(last == first-1) condition always gives exception, since you are trying to read an index before the first position. To find out if the iterator has reached 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);
    }
}