mercredi 11 novembre 2020

how to use upper_bound to find out the last variable that satisfies a certain condition

I'm trying to use a log(n) method to find out the last variable that satisfies a certain condition. I looked at the documentation and found these in the algorithm section (http://www.cplusplus.com/reference/algorithm/)

Binary search (operating on partitioned/sorted ranges):

lower_bound: Return iterator to lower bound (function template )

upper_bound: Return iterator to upper bound (function template )

equal_range: Get subrange of equal elements (function template )

binary_search: Test if value exists in sorted sequence (function template )

I think to do what I'm trying to do, I should use upper_bound/lower_bound.

In this case, I'm trying to find out the last index of the number that is smaller or equal to 3. (3). I know there are simpler ways such as looping through the whole array, but I want to learn how to use upper_bound. I know that the comparator needs 2 numbers but I don't need 2 numbers so I'm not sure what to do.

#include <bits/stdc++.h>

using namespace std;
vector<int> a = {0,1,2,3,4,5};
bool check(int base) {
    if (a.at(base)  <= 3) {
        return true;
    }
    return false;
}

int main() {
    int c;
    sort(a.begin(), a.end());
    c = distance(a.begin(), upper_bound(a.begin(), a.end(), check));
    cout<<c;
    return 0;
}

How would I correctly do this?

Aucun commentaire:

Enregistrer un commentaire