STL二分查找算法

用binary_search进行二分查找

 

用法一:在从小到大排好序的基本类型数组上进行二分查找
binary_search(数组名+n1,数组名+n2,值);
n1和n2都是int类型的表达式,可以包含变量
如果n1=0,则 + n1可以不写
查找区间为下标范围为[n1,n2)的元素,下标为n2的元素不在查找区间内 在该区间内查找”等于”值”的元素,返回值为true(找到)或false(没找到)
“等于”的含义: a 等于 B <=> a < b和b < a都不成立

 

用法二:在用自定义排序规则排好序的、元素为任意的T类型的数组中进行二分查找
binary_search(数组名+n1,数组名+n2,值,排序规则结构名());
查找时的排序规则,必须和排序时的规则一致!
binary_search用法实例:

输出结果:

3,7,12,21,45,98,
result:1
result:0
21,12,3,45,7,98,
result:0
result:1

用lower_bound二分查找下界

 

用法一:在对元素类型为T的从小到大排好序的基本类型的数组中进行查找
T * lower_bound(数组名+n1,数组名+n2,值);
返回一个指针 T * p;
*p 是查找区间里下标最小的,大于等于”值” 的元素。如果找不到,p指向下标为n2
的元素

 

用法二:在元素为任意的T类型、按照自定义排序规则排好序的数组中进行查找
T * lower_bound(数组名+n1,数组名+n2,值,排序规则结构名());
返回一个指针 T * p;
*p 是查找区间里下标最小的,按自定义排序规则,可以排在”值”后面的元素。如果找
不到,p指向下标为n2的元素
用upper_bound二分查找上界

 

用法一:在元素类型为T的从小到大排好序的基本类型的数组中进行查找
T * upper_bound(数组名+n1,数组名+n2,值);
返回一个指针 T * p;
*p 是查找区间里下标最小的,大于”值”的元素。如果找不到,p指向下标为n2的元素

 

用法二:在元素为任意的T类型、按照自定义排序规则排好序的数组中进行查找
T * upper_bound(数组名+n1,数组名+n2,值,排序规则结构名());
返回一个指针 T * p;
*p 是查找区间里下标最小的,按自定义排序规则,必须排在”值”后面的元素。如果找
不到,p指向下标为n2的元素
lower_bound,upper_bound用法示例: