lower_bound 和 upper_bound函数的使用

头文件：lower_bound和upper_bound在头文件algorithm中；
lower_bound和upper_bound为二分法查找元素，其时间复杂度为O(log n)。

一、数组中的lower_bound和upper_bound

对于一个排序数组 nums[5]{1, 2, 5, 7, 9};

（1） int i = lower_bound(nums, nums + n, val) - nums;

函数解释：lower_bound函数返回数组 nums 中大于等于 val 的第一个元素的地址，若 nums 中的元素均小于 val 则返回尾后地址。

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

int main()
{
    const int n = 5;
    int nums[n]{ 1,2,5,7,9 };
    int i = lower_bound(nums, nums + n, 6) - nums;//大于等于6
    cout << i << endl;//i=3
    int j = lower_bound(nums, nums + n, 10) - nums;
    cout << j << endl;//j=5

    system("pause");
    return 0;
}

（2） int i = upper_bound(nums, nums + n, val) - nums;

函数解释：upper_bound函数返回数组 nums 中大于 val 的第一个元素的地址，若 nums 中的元素均小于等于 val 则返回尾后地址。

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

int main()
{
    const int n = 5;
    int nums[n]{ 1,2,5,7,9 };
    int i = upper_bound(nums, nums + n, 6) - nums;//大于6
    cout << i << endl;//i=3
    int j = upper_bound(nums, nums + n, 9) - nums;
    cout << j << endl;//j=5

    system("pause");
    return 0;
}

二、STL中的lower_bound和upper_bound

用法和数组中的用法基本一样，不同之处在于写法和返回值，STL返回值为迭代器，写法如下：

（1）vector

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

int main()
{
    vector<int> vec{ 1,2,5,7,9 };//有序数组
    vector<int>::iterator it1 = lower_bound(vec.begin(), vec.end(), 9);
    bool flag1 = it1 == vec.end() - 1;
    cout << flag1 << endl;//it1指向最后一个元素的迭代器
    vector<int>::iterator it2 = upper_bound(vec.begin(), vec.end(), 9);
    bool flag2 = it2 == vec.end();
    cout << flag2 << endl;//it2为尾后迭代器

    system("pause");
    return 0;
}

（2）set

#include<iostream>
#include<algorithm>
#include<set>
using namespace std;

int main()
{
    set<int> s{ 1,2,1,9,7 };//原本就有序
    set<int>::iterator it1 = s.lower_bound(2);
    cout << *it1 << endl;//*it1=2
    set<int>::iterator it2 = s.upper_bound(2);
    cout << *it2 << endl;//*it2=7

    system("pause");
    return 0;
}

（3）map

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;

int main()
{
    map<int, int> m{ {1,2},{2,2},{1,2},{9,2},{7,2} };//有序
    map<int, int>::iterator it1 = m.lower_bound(2);
    cout << it1->first << endl;//it1->first=2
    map<int, int>::iterator it2 = m.upper_bound(2);
    cout << it2->first << endl;//it2->first=7

    system("pause");
    return 0;
}