最近又用闲暇时间把STL中二分查找学了一点。趁热打铁，总结一下我学习队列时候所遇到的知识点。反正写这玩意也没人看，就当做我个人学习的复习和总结吧
本人水平有限，如果有问题欢迎指出，不吝赐教。
一、二分查找
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。二分查找要求必须使用顺序排列，而且要求表中元素按关键字有序排列。时间复杂度O（log2n）。
二、查找过程
首先、我们先假设排列对象为升序排列（从小到大），然后将表中间的数字与查找对象进行比较，如果两者相等，则查找成功；否则利用中间位置将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的数据，使查找成功，或直到子表不存在为止，此时查找不成功。
（如图）
二分查找和快速排序都利用了分治的思想，即就是把一个复杂的问题分成两个或多个相同或相似的子问题，再把子问题分成更小的子问题直到最后子问题，来简单地直接求解。
根据这些原理，我们就可以很快写出一段程序
#include<bits/stdc++.h> // 万能库using namespace std;int find(int *a,int x){int l=1,r=n;while(l<=r){int mid=(r+l)/2;if(a[mid]==x) return mid; // 如果啊a[mid]==x,返回mid值else if(a[mid]>x) r=mid-1; // 如果值大于中值，则在左半寻找else l=mid+1; // 如果值小于中值，则在右半寻找}else return -1;// 没找到返回-1}
四、STL库中的二分查找
这段是本文的重点,教你如何使用STL库来完成二分查找。同样的，这个函数储存在<algorithm>之中，他们分别是。
upper_bound(begin,end,val)
lower_bound(begin,end,val)
它们两个都会在[begin,end)之间查找目标，必须在已经排序的数组中使用，那么他们两个有什么区别呢？
upper_bound会返回数组中第一个大于被查数的值（不一定等于被查数），而lower_bound查找的是大于或者等于目标值的元素。将查找到的地址减去头的地址，就可以得到其在数组中的位置；如果你需要知道其出现了多少次upper_bound（···）-lower_bound(···)就可以知道其出现了多少次。
（这里需要一点地址的知识，不懂可以看这篇第一节C语言的灵魂----指针
）
例子：
#include<bits/stdc++.h>using namespace std;int main() {int a[9]={1,2,3,3,3,4,5,6,7};cout<<upper_bound(a,a+9,3)<<endl; // 查找第一个大于的地址cout<<lower_bound(a,a+9,3)<<endl; // 查找第一个的地址cout<<upper_bound(a,a+9,3)-a<<endl; // 查找第一个大于在数组的位置cout<<lower_bound(a,a+9,3)-a<<endl; // 查找第一个在数组的位置cout<<upper_bound(a,a+9,3)-lower_bound(a,a+9,3); // 查找出现几次return 0;}
运行结果
可以看到返回了正确的结果。
这大概就是STL中二分查找简单的用法，在日常中还是要多多练习才能掌握。文章最后祝大家学业有成，不断进步
如果觉得写的好欢迎点个赞，加个关注呗
