STL中的二分查找法--算法--笔记

binary_search

用binary_search进行二分法查找(用法一)
方法：binary_search(数组名+n1,数组名+n2,值);
注：

1：n1和n2都是int类型的表达式，可以包含变量，如果n1=0,则+n1可以不写
查找区间为下标范围为[n1.n2)的元素，下标为n2的元素不在
在该区间内查找"等于"值的元素，返回值为true(找到)或false(没找到)

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

用binary_search进行二分查找(用法二)

在用自定义排序好的，元素为任意的T类型的数组中进行二分查找
方法：binary_search(数组名+n1，数组名+n2，值，排序规则结构名());

n1和n2都是int类型的表达式，可以包含变量
如果n1=0,则+n1可以不写
查找区间为下标范围[n1,n2)的元素，下表为n2的元素不在查找区间内
在该区间内查找等于值的元素，返回值为true(找到)或false(没找到)

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

int main(){
int a[]={12,45,3,98,21,7};
sort(a,a+6);
Print(a,6);
cout<<"result"<<binary_search(a,a+6,12)<<endl;
cout<<"result"<<binary_search(a,a+6,77)<<endl;
sort(a,a+6,Rule());//按个位数从小到大
Print(a,6);
cout<<"result"<<binary_search(a,a_6,7)<<endl;
cout<<"result"<<binary_search(a,a+6,8,Rule())<<endl;
return 0;
}
result:1
result:0
21,12,3,45,7,98,
result:0
result:1//为什么元数据中没有8还返回了了1呢。因为是按照个位查找的数

lower_bound

用lower_bound二分查找下界(用法一)
在对元素类型为T的从小到大排好序的基本类型的数组中进行查找
方法：T*lower_bound(数组名+n1,数组名+n2,值)；

返回一个指针T*P;
*p是查找区间里下标最小的，大于等于值的元素，如果找不到，p指向下表为n2的元素

用lower_bound二分查找下界(用法二)
在元素为任意的T类型，按照自定义排序规则排好序的数组中进行查找
方法：T*lower_bounde(数组名+n1,数组名+n2,值，排序规则结构名());

返回一个指针T*P;
*p是查找区间里下标最小的，按自定义排序规则，可以排在值后面的元素，如果找不到，p指向下标为n2的元素

upper_bound

用upper_bound二分查找上界(用法一)
在元素类型为T的从小到大排好序的基本类型的数组中进行查找
用法：T*upper_bound(数组名+n1,数组名+n2,值)；

返回一个指针T*P;
*p是查找区间下标最小的，大于"值的元素，如果找不到，p指向下标为n2的元素"

用upper_bound二分查找上界(用法二)
在元素类型为T,按照自定义排序规则的数组中进行查找
方法：T*upper_bound(数组名+n1,数组名+n2,值,排序规则结构名())；

返回一个指针T*P;
*p是查找区间下标最小的，按照自定义规则，必须排在值后面的元素，如果找不到，p指向下标为
n2的元素"

low_bound,upper_bound

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
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<<a[i]<<" ,";
 }
 cout<<endl;
}
#define NUM 7;
int main(){
int a[NUM]={12,5,3,5,98,21,7};
sort(a,a+NUM);
Print(a,NUM);//=>3,5,5,7,12,21,98,
int *p=lower_bound(a,a+NUM,5);
cout<<*p<<" ,"<<p-a<<endl;//=>5,1
p=upper_bound(a,a+NUM,5);
cout<<*p<<endl;//=>7
cout<<*upper_bound(a,a+NUM,13)<<endl;//=>21
sort(a,a+NUM,Rule());//按照个位数排序了
Print(a,NUM);//=>21,12,3,5,5,7,98;
cout<<*lower_bound(a,a+NUM,Rule())<<endl;//=>7
cout<<lower_bound(a,a+NUM,25,Rule())-a<<endl;//=>3
cout<<upper_bound(a,a+NUM,18,Rule())-1<<endl;//=>7
if(upper_bound(a,a+NUM,18,Rule())==a+NUM)
 cout<<"not found"<<endl;//=>not found
 cout<<*upper_bound(a,a+NUM,5,Rule())<<endl;//=>7
 cout<<*upper_bound(a,a+NUM,4,Rule())<<endl;//=>5
 return 0;
}