C++STL标准库学习笔记（二）二分查找

C++STL标准库学习笔记（二）二分查找 二、STL中的二分查找算法

binary_search

lower_bound

upper_bound

记得#include

前言：

在这个笔记中，我把大多数代码都加了注释，我的一些想法和注解用蓝色字体标记了出来，重点和需要关注的地方用红色字体标记了出来。

1.1用binary_search进行二分查找（用法一）

在从小到大排好序的基本类型数组上进行二分查找

binary_search(数组名+n1, 数组名+n2,值);

n1和n2都是int类型表达式，可以包含变量

如果n1=0，则 + n1可以不写（这几点和前面sort一样）

查找区间为下标范围为[n1,n2)的元素，下标为n2的元素不在查找区间内，在该区间内查找“等于”值的元素，返回值为true（找 到）或false（没找到）。（返回值不是位置哦）

等于的含义：a等于b <=> a

不是a==b！

1.2用binary_search进行二分查找（用法二）

在用自定义排序规则排好序的、元素为任意的T类型的数组中进行二分查找。

binary_search(数组名+n1, 数组名+n2, 值, 排序规则结构名());

n1和n2都是int类型表达式，可以包含变量

如果n1=0，则 + n1可以不写

查找区间为下标范围为[n1,n2)的元素，下标为n2的元素不在查找区间内，在该区间内查找“等于”值的元素，返回值为true（找 到）或false（没找到）。

查找时的排序规则，必须和排序时的规则一致！

也不是说排序规则不一样就一定找不到，有可能找到，但是找到的结果并没有意义，说不定就是运气好找到了。

等于的含义：a等于b <=> a

样例：

struct Rule//按个位数从小到大排

{

    bool operator()(const int & a1, const int & a2)const{

        return a1%10 < a2%10;

    }

};

void Print(int a[],int size)

{

    for (int i = 0; i < size; i++)

    {

        cout<

2.1用lower_bound二分查找下界（用法一）

在对元素类型为T的从小到大排好序的基本类型的数组中进行查找

T * lower_bound(数组名+n1, 数组名+n2, 值);

返回一个指针 T * p;

*p 是查找区间里下标最小的，大于等于值的元素。如果找不到，p指向下标为n2的元素。（反正n2不在查找区间内，要是要写判断可以用这个作为依据）

2.2用lower_bound二分查找下界（用法二）

在元素为任意的T类型、按照自定义排序规则排好序的数组中进行查找

T * lower_bound(数组名+n1, 数组名+n2, 值, 排序规则名());

返回一个指针 T * p;

*p是查找区间里下标最小的，按自定义排序规则，可以排在“值”后面的元素。如果找不到，p指向下标为n2的元素。

3.1用upper_bound二分查找上界（用法一）

在对元素类型为T的从小到大排好序的基本类型的数组中进行查找

T * upper_bound(数组名+n1, 数组名+n2, 值);

返回一个指针 T * p;

*p 是查找区间里下标最小的，大于值的元素。如果找不到，p指向下标为n2的元素。（这里是大于，不要和前面弄混了）

3.2用upper_bound二分查找上界（用法二）

在元素为任意的T类型、按照自定义排序规则排好序的数组中进行查找

T * upper_bound(数组名+n1, 数组名+n2, 值, 排序规则名());

返回一个指针 T * p;

*p是查找区间里下标最小的，按自定义排序规则，必须排在“值”后面的元素。如果找不到，p指向下标为n2的元素。（这里是必须排在值后面的元素，相对来说，lower_bound是可以排在值后面，有可能等于，但是这个就不可能等于了）

样例：（这个样例挺全，各种情况都有）

//lower_bound是找到的下标最小的，按排序规则，大于等于值的元素

//upper_bound是找到的下标最小的，按排序规则，必须排在值后面的元素

//两个都是找不到就指向下标为n2的元素

struct Rule//按个位数从小到大排

{

    bool operator()(const int & a1, const int & a2)const{

        return a1%10 < a2%10;

    }

};

void Print(int a[],int size)

{

    for (int i = 0; i < size; i++)

    {

        cout<

后记：

又学完一节，不得不说STL标准库确实好用，但是平常记不记得用就是个难题了，很多时候我们的思维都固化了，勇敢的尝试新事物有助于我们能力的提升（指想得到用刚学的STL标准库），而在这跳出舒适区的过程中，我们也会收获成长的快乐，总之感谢大家读到这里，我run了，祝大家健康快乐吉祥如意恭喜发财学业有成早生贵子，以及头发茂密，下篇博客再见拜拜。