[C++] lower_bound & upper_bound

1. bound

 

해당 함수는 정렬된 배열에서만 사용하도록 하자!

 

#include<iostream>
#include<vector>
using namespace std;

// return iterator
// Must only be used in an ordered array.
int main(){
    vector<int> a {1,2,3,3,3,4};
    // where the 3 is located. (count from 0)
    cout << lower_bound(a.begin(), a.end(), 3) - a.begin() << endl;
    // 2
    cout << upper_bound(a.begin(), a.end(), 3) - a.begin() << endl;
    // 5
    return 0;
}

#include<iostream>
#include<vector>
using namespace std;

int main () {
    vector<int> a {1,2,3,3,3,4};
    cout <<"lower_bound(a.begin(), a.end(),3) : "<< &*lower_bound(a.begin(), a.end(), 3) << endl;
    cout << "a.begin() : "<< &*a.begin() << endl;
    cout << "a.begin() + 1 : " << &*(a.begin() + 1) << endl;

    cout << "&*lower_bound(a.begin(), a.end(), 3) - &*a.begin() : ";
    cout << &*lower_bound(a.begin(), a.end(), 3) - &*a.begin() << endl;
    cout << "lower_bound(a.begin(), a.end(), 3) - a.begin() : ";
    cout << lower_bound(a.begin(), a.end(), 3) - a.begin() << endl;

    cout << "(a.begin() + 2) - a.begin() : ";
    cout << (a.begin() + 2) - a.begin() << endl;
    return 0;
}
/*
lower_bound(a.begin(), a.end(),3) : 0x6000009c5128
a.begin() : 0x6000009c5120
a.begin() + 1 : 0x6000009c5124
&*lower_bound(a.begin(), a.end(), 3) - &*a.begin() : 2
lower_bound(a.begin(), a.end(), 3) - a.begin() : 2
(a.begin() + 2) - a.begin() : 2
*/

• lower_bound(), upper_bound() 모두 이터레이터를 반환한다.
• lower_bound(a.begin(), a.end(), 3) - a.begin() : 배열에서 3이 위치한 첫 번째와 마지막 자리를 알기 위해서는 시작값을 빼야 한다.

#include<iostream>
#include<vector>
using namespace std;

vector<int> a {1,2,3,3,3,3,4,100};
int count(){
    cout << upper_bound(a.begin(), a.end(), 3) - lower_bound(a.begin(), a.end(), 3) << endl;
    return 0;
}

int near(){
    vector<int> v;
    for (int i=2; i <=5; i++) v.push_back(i);
    v.push_back(7);
    //2 3 4 5 7
    //0 1 2 3 4
    // 찾는 값이 없으면 가장 가까운 값 중 가장 큰 값에 의 iterator 반환
    cout << upper_bound(v.begin(), v.end(), 6) - v.begin() << endl;
    //4 (7보단 작고 6은 없고 5보단 크고)
    cout << lower_bound(v.begin(), v.end(), 6) - v.begin() << endl;
    //4 (5보단 크고 6은 없고 7보단 작고)
    cout << upper_bound(v.begin(), v.end(), 9) - v.begin() << endl;
    //5 (7보다 커서)
    cout << lower_bound(v.begin(), v.end(), 9) - v.begin() << endl;
    //5 (7보다 커서)
    cout << upper_bound(v.begin(), v.end(), 0) - v.begin() << endl;
    //0 (2보다 작아서)
    cout << lower_bound(v.begin(), v.end(), 0) - v.begin() << endl;
    //0 (2보다 작아서)
    return 0;
}

int main(){
    count();
    near();
}
/*
4
4
4
5
5
0
0
*/

만약 원소를 찾을 때 못 찾을 경우에는 찾는 값이 없으면 가장 가까운 값 중 가장 큰 값의 iterator 반환한다.

 

---