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

二、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了，祝大家健康快乐吉祥如意恭喜发财学业有成早生贵子，以及头发茂密，下篇博客再见拜拜。

巴特西

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

最新文章

热门文章