前言

二分，其实大家也应该听说过，如果接触过竞赛什么的，这个东西几乎是第一个学习的基础算法。
本人学习浅薄，没有学习其他的技术知识，仅仅想把我的理解分享给大家。

如果大家在数学课上学过函数的话，那就可能接触过二分这个大名。他在求函数零点的近似值时有用到过，上课的时候你可能会想，这玩意考试又不考，又算不上高阶技巧，为何老师要讲这个东西呢？其实老师只是讲了二分的一个用处，而二分在计算机算法上有着更加广阔的天地，传说中能正确写对二分的程序员可以年薪百万哦（瞎说的

那么接下来我将讲讲二分关于二分查找和二分答案的应用。

二分查找

假设我们现在有一堆的数字，我们应该如何确定数字x是否在这堆数字中呢？
最简单的方法就是一个一个数字去找，看他和x是不是一样的。
但是如果这堆数字多得离谱，以亿万记，这个时候查找就会相当的慢了。
那有没有方法可以优化他呢？
二分查找就是一个很好的选择。

二分查找首先得保证这堆数字有序，如上图，这个时候就有杠精要问了，我都排序了，还不知道哪些数字有，哪些数字没有吗？ 当然可以知道，但是这样你只能查找一次，如果你想查找下一次的话就得再来一次，完全做不到有效的信息利用，而二分就是利用有序这个信息进行工作的。

我们设这个有序数列为数组a，数组中第i个数记为a[i]，顺序从小到大。

二分首先需要一个范围分别是l,r，代表着二分的查找范围是从第l个数到第r个数。l，我们称之为二分的左边界。r，我们称之为二分的右边界。
每一次，我们取l和r的平均值（取整）mid=（l+r）/2,判断a[mid]是否大于x，如果a[mid]>x，那么根据有序性，我们可以判定数字x不在第mid位数和第r位数之间，因为这些数a[i]>=a[mid]>x。
同理，如果a[mid]<x,则数字x不在第l位数和第mid位数之间，因为这些数字满足a[i]<=a[mid]<x
如果a[mid]=x,那么恭喜你找到他了。

如果你深入理解这个东西，你就会发现他每次都会至少缩小一半的搜索范围，因为一个数字p关于数字x只可能有三种状态：

               p<x  或  p>x  或p=x。

所以如果我们在有序数列中任取一个数p，都可以通过有序性确定x究竟在p的左边还是右边，而如果你取得数字恰好就是中位数，那么你一次就可以稳定的排除搜索范围中一半的数字，只因为数字x只可能出现在p的一侧，而另一侧就可以排除。

如果有人看到这里，可能会问出这样的问题：
可是我每次操作只确定了数字x的所在范围，却没有确定数字x的位置啊！

糊涂啊！如果数字边界l=r，不就说明了只剩下一个数了吗？，如果这个数字不等于x，就说明数字x不存在！

以下是模拟二分搜索!

暂时就到这里。我们下次来讲实现时的细节。

代码如下

include<bits/stdc++.h>

using namespace std;
int a[1000000]; //数组a
int n; //数字的个数
int x; //查找数字x
int q; //查询次数q
bool cmp(int a1,int a2){

return a1<a2;

}

int check(int find){

int l=1,r=n;
while(l<r){
    int mid=(l+r+1)>>1;
    if(a[mid]>find)r=mid-1;
    else l=mid;
}
if(a[l]!=find) return -20;
else return l;

}
int main(){

cout<<"请输入数字的个数：\n"; 
cin>>n;

cout<<"请输入数字：\n";
for(int i=1;i<=n;++i){
    cin>>a[i];
}
sort(a+1,a+1+n,cmp);      //排序：顺序从小到大 
cout<<"请输入查询次数：\n";
 cin>>q;
 for(int i=1;i<=q;++i){
     cin>>x;
     if(check(x)<=0)cout<<"该数不存在\n";
     else cout<<"这个数存在，排序后位置为 "<<check(x)<<endl;
 }
return 0;

}