二、STL中的二分查找算法
1.binary_search
2.lower_bound
3.upper_bound
记得#include<algorithm>!
前言：
在这个笔记中，我把大多数代码都加了注释，我的一些想法和注解用蓝色字体标记了出来，重点和需要关注的地方用红色字体标记了出来。
1.1用binary_search进行二分查找（用法一）
在从小到大排好序的基本类型数组上进行二分查找
binary_search(数组名+n1, 数组名+n2,值);
n1和n2都是int类型表达式，可以包含变量
如果n1=0，则 + n1可以不写（这几点和前面sort一样）
查找区间为下标范围为[n1,n2)的元素，下标为n2的元素不在查找区间内，在该区间内查找“等于”值的元素，返回值为true（找 到）或false（没找到）。（返回值不是位置哦）
等于的含义：a等于b <=> a<b和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<b和b<a都不成立。
样例：
1 struct Rule//按个位数从小到大排
2 {
3 bool operator()(const int & a1, const int & a2)const{
4 return a1%10 < a2%10;
5 }
6 };
7 void Print(int a[],int size)
8 {
9 for (int i = 0; i < size; i++)
10 {
11 cout<<a[i]<<",";
12 }
13 cout<<endl;
14 }
15
16 int main(int argc, char const *argv[])
17 {
18 int a[] = {12,45,3,98,21,7};
19 sort(a,a+sizeof(a)/sizeof(int));//从小到大排序
20 Print(a,sizeof(a)/sizeof(int));//结果：3,7,12,21,45,98,
21 cout<<"result:"<<binary_search(a,a+6,12)<<endl;//结果：1
22 cout<<"result:"<<binary_search(a,a+6,77)<<endl;//结果：0
23 sort(a,a+6,Rule());
24 Print(a,6);//结果：
25 cout<<"result:"<<binary_search(a,a+6,7)<<endl;//结果：0//其实能找到结果，但是这是没意义的，运气好找到罢了。
26 cout<<"result:"<<binary_search(a,a+6,8,Rule())<<endl;//结果：1
27 //这个结果是1，因为'='的含义是a在b前面和b在a前面都不成立，不是“==”！这里其实找到的是98。
28 return 0;
29 }
样例
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是可以排在值后面，有可能等于，但是这个就不可能等于了，详情可以看样例）
样例：（这个样例挺全，各种情况都有）
1 //lower_bound是找到的下标最小的，按排序规则，大于等于值的元素
2 //upper_bound是找到的下标最小的，按排序规则，必须排在值后面的元素
3 //两个都是找不到就指向下标为n2的元素
4 struct Rule//按个位数从小到大排
5 {
6 bool operator()(const int & a1, const int & a2)const{
7 return a1%10 < a2%10;
8 }
9 };
10 void Print(int a[],int size)
11 {
12 for (int i = 0; i < size; i++)
13 {
14 cout<<a[i]<<",";
15 }
16 cout<<endl;
17 }
18
19 int main(int argc, char const *argv[])
20 {
21 int a[NUM] = {12,5,3,5,98,21,7};
22 sort(a,a+sizeof(a)/sizeof(int));//从小到大排序
23 Print(a,sizeof(a)/sizeof(int));//结果：3,5,5,7,12,21,98
24 int *p = lower_bound(a,a+NUM,5);
25 cout<<*p<<","<<p-a<<endl;//结果：5,1
26 p = upper_bound(a,a+NUM,5);
27 cout<<*p<<endl;//结果：7
28 cout<<*upper_bound(a,a+NUM,13)<<endl;//结果：21
29 //这里可以看见不用查找数组内存在的元素也有返回值，当然，这里用binary_search()就会返回false了
30 sort(a,a+NUM,Rule());
31 Print(a,NUM);//结果：21,12,3,5,5,7,98,
32 cout<<* lower_bound(a,a+NUM,16,Rule())<<endl;//结果：7
33 cout<< lower_bound(a,a+NUM,25,Rule())-a<<endl;//结果：3//这里结果是下标
34 cout<< upper_bound(a,a+NUM,18,Rule())-a<<endl;//结果：7//这里结果也是下标，毕竟没找到
35 if (upper_bound(a,a+NUM,18,Rule())==a+NUM)
36 {
37 cout<<"not found"<<endl;//not found，这里是一个例子，如何判断没有找到
38 }
39 cout<<*upper_bound(a,a+NUM,5,Rule())<<endl;//结果：7
40 cout<<*upper_bound(a,a+NUM,4,Rule())<<endl;//结果：5
41 return 0;
42 }
样例
后记：
又学完一节，不得不说STL标准库确实好用，但是平常记不记得用就是个难题了，很多时候我们的思维都固化了，勇敢的尝试新事物有助于我们能力的提升（指想得到用刚学的STL标准库），而在这跳出舒适区的过程中，我们也会收获成长的快乐，总之感谢大家读到这里，我run了，祝大家健康快乐吉祥如意恭喜发财学业有成早生贵子，以及头发茂密，下篇博客再见拜拜。