C++STL标准库学习笔记(二)二分查找
二、STL中的二分查找算法
1.binary_search
2.lower_bound
3.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
样例:
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<","; 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:"<样例6,12)< //结果:1 22 cout<<"result:"< 6,77)< //结果:0 23 sort(a,a+6,Rule()); 24 Print(a,6);//结果: 25 cout<<"result:"< 6,7)< //结果:0//其实能找到结果,但是这是没意义的,运气好找到罢了。 26 cout<<"result:"< 6,8,Rule())< //结果: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<","; 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<<","<样例//结果:5,1 26 p = upper_bound(a,a+NUM,5); 27 cout<<*p< //结果:7 28 cout<<*upper_bound(a,a+NUM,13)< //结果: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())< //结果:7 33 cout<< lower_bound(a,a+NUM,25,Rule())-a< //结果:3//这里结果是下标 34 cout<< upper_bound(a,a+NUM,18,Rule())-a< //结果:7//这里结果也是下标,毕竟没找到 35 if (upper_bound(a,a+NUM,18,Rule())==a+NUM) 36 { 37 cout<<"not found"< //not found,这里是一个例子,如何判断没有找到 38 } 39 cout<<*upper_bound(a,a+NUM,5,Rule())< //结果:7 40 cout<<*upper_bound(a,a+NUM,4,Rule())< //结果:5 41 return 0; 42 }
后记:
又学完一节,不得不说STL标准库确实好用,但是平常记不记得用就是个难题了,很多时候我们的思维都固化了,勇敢的尝试新事物有助于我们能力的提升(指想得到用刚学的STL标准库),而在这跳出舒适区的过程中,我们也会收获成长的快乐,总之感谢大家读到这里,我run了,祝大家健康快乐吉祥如意恭喜发财学业有成早生贵子,以及头发茂密,下篇博客再见拜拜。