和二分有关的三个STL库函数

## 二分查找 #### 二分查找也称折半查找，它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。 #### 关键代码： ```cpp int search(int *arr,int l,int r,int k) { //l,r,为要找的区间,k为要找的数,arr为要在中间查找的数组 while (l<=r) { /*找到直接返回坐标*/ if (arr[l]==k) return l; if (arr[r]==k) return r; mid=(l+r)/2; //求出中间的坐标 if (k<arr[mid]) r=mid-1; //如果要找的数小于数组中间的数,把右坐标调整到mid的左边一个 else l=mid+1; //否则把左坐标调整到mid的右边一个 } } ``` ------------ # 下面看正题 ------------ ## 三个函数 ------------ ### * binary_search * ##### 函数原型：binary_search(first,last,val) ###### 表示在[first,last)中寻找一个值为val的数，若存在，返回true，否则返回false ### 举个栗子： ```cpp #include<iostream> #include<algorithm> using namespace std; int arr[6]={1,3,4,7,9}; int main(){ int k; cin>>k; cout<<binary_search(arr,arr+5,k); return 0; } ``` 如果输入1，结果会输出1 如果输入2，结果会输出0 如果输入3，结果会输出1 …… 在数组中出现过的，都会输出1 没出现过的，都会输出0 不过用之前得保证数组里的数都是递增的哦，有时候需要先排序才能用 ------------ ### * lower_bound * ##### 函数原型：lower_bound(first,last,val)-array/iterator ###### 表示在[first,last)中寻找 _第一个大等于_ val的数，返回其下标 ### 举个栗子： ```cpp #include<iostream> #include<algorithm> using namespace std; int arr[6]={1,3,4,7,9}; int main(){ int k; cin>>k; cout<<lower_bound(arr,arr+5,k)-arr; return 0; } ``` 如果输入2，则会输出1（数值3在数组中出现的位置） 如果输入3，则会输出1（数值3在数组中出现的位置） 如果输入4，则会输出2（数值4在数组中出现的位置） …… 用之前也得排序，而且要把它和upper_bound分清楚哦 ------------ ### * upper_bound * ##### 函数原型：upper_bound(first,last,val)-array/iterator ###### 表示在[first,last)中寻找 _第一个大于_ val的数，返回其下标 ### 举个栗子： ```cpp #include<iostream> #include<algorithm> using namespace std; int arr[6]={1,3,4,7,9}; int main(){ int k; cin>>k; cout<<lower_bound(arr,arr+5,k)-arr; return 0; } ``` 如果输入2，则会输出1（数值3在数组中出现的位置） 如果输入3，则会输出2（数值4在数组中出现的位置） 如果输入4，则会输出3（数值7在数组中出现的位置） …… ------------ #### 温馨提示： ###### [first,last)：左闭右开区间，表示取的一个数x，取值范围是first <= x < last ###### array/iterator：数组/迭代器，这里表示删除数组或迭代器，返回下标地址