STL二分查找法

用binary_search进行二分查找（用法一）

• 在从小到打排好序的基础类型数组上进行二分查找

  binary_search(数组+n1，数组名+n2,值)；

  n1和n2都是int 类型的表达式，可以包含变量

  如果n1=0，则+n1可以不写

查找区间为下标范围为[n1,n2)的元素，下标为n2的元素不在查找区间内在该区间内查找等于”值“的元素，返回值为true(找到)或者false（没找到）

等于的含义不是简单的==，真实含义是：a等于b <=> a<b 和 b<a 都不成立

用binary_search进行二分查找（用法二）

• 在用自定义排序规则排好序的，元素为任意的T类型的数组中进行二分查找

  binary_search(数组名+n1,数组名+n2,值，排序规则结构名)；

  ​ n1和n2都是int类型的表达式，可以包含变量

  ​ 如果n1=0，则可以不写

查找区间为下标范围为[n1,n2)的元素，下标为n2的元素不在查找区间内在该区间内查找”等于“值的元素，返回值为true（找到）或false（没找到）

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

”等于“的含义：a等于b <=>"a必须在b前面"和”b必须在a前面“都不成立

例子：

#include <cstdio>
#include <cstring>
#include <iostream>
#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;
	}
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;
}

用lower_bound二分法找下界（用法一）

• 在对元素类型为T的从小到大排好序的基本类型的数组中进行查找

  ​ T*lower_bound(数组+n1,数组+n2,值)；

  ​ 返回一个指针T*p;

  *p是查找区间里下标最小的，且大于等于”值“的元素。如果找不到，p指向下标为n2的元素。

用lower_bound二分法找下界（用法二）

• 在对元素类型为T的从小到大排好序的基本类型的数组中进行查找

  ​ T*lower_bound(数组+n1,数组+n2,值，排序规则结构名（)）；

  ​ 返回一个指针T*p;

  排序和查找的规则要一样

  *p是查找区间里下标最小的，按自定义排序规则，可以排在”值“后面的元素。如果找不到，p指向下标为n2的元素。

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的元素

用法示例：

#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,16,rule())<<endl;
    cout<<lower_bound(a,a+NUM,25,rule())-a<<endl;
    cout<<upper_bound(a,a+NUM,18,rule())-a<<endl;
    if(upper_bound(a,a+NUM,18,rule())==a+NUM)
        cout<<"not found"<<endl;
    cout<<*upper_bound(a,a+NUM,5,rule())<<endl;
    cout<<*upper_bound(a,a+NUM,4,rule())<<endl;
    return 0;
}