分治算法
算法介绍
所谓分治就是指的分而治之，即将较大规模的问题分解成几个较小规模的问题，通过对较小规模问题的求解达到对整个问题的求解。当我们将问题分解成两个较小问题求解时的分治方法称之为二分法。
你们玩过猜数字的游戏吗？你的朋友心里想一个1000以内的正整数，你可以给出一个数字x，你朋友只要回答“比x大”或者“比x小”或者“猜中”，你能保证在10次以内猜中吗？运气好只要一次就猜中。
开始猜测是1到1000之间，你可以先猜500，运气好可以一次猜中，如果答案比500大，显然答案不可能在1到500之间，下一次猜测的区间变为501到1000，如果答案比500小，那答案不可能在500到1000之间，下一次猜测的区间变为1到499。只要每次都猜测区间的中间点，这样就可以把猜测区间缩小一半。因此不超过10次询问区间就可以缩小为1，答案就会猜中了，这就是二分的基本思想。
每一次使得可选的范围缩小一半，最终使得范围缩小为一个数，从而得出答案。假设问的范围是1到n，所以我们只需要问O(logn)次就能知道答案了。
需要注意的是使用二分法有一个重要的前提，就是有序性，下面通过几个例子来体会二分法的应用。
例题
1.找数
描述：
给一个长度为n的单调递增的正整数序列，即序列中每一个数都比前一个数大。有m个询问，每次询问一个x，问序列中最后一个小于等于x的数是什么？
输入：
第一行两个整数n,m。
接下来一行n个数，表示这个序列。
接下来m行每行一个数，表示一个询问。
输出：
输出共m行，表示序列中最后一个小于等于x的数是什么。假如没有输出-1。
样例输入：
5 3
1 2 3 4 6
5
1
3
样例输出：
4
1
3
分析
我们用Left表示询问区间的左边界，用Right表示询问区间的右边界，[Left,Right]组成询问区间。一开始Left=1，Right=n，我们可以把原始序列的左边想象成若干个无穷小的数，把序列的右边想象成无穷大的数，这样比较好理解。序列已经按照升序排好，保证了二分的有序性。
每一次二分，我们这样来做：
①取区间中间值Mid=(Left+Right)/2；
②判断Mid与x的关系，如果a[Mid]>x，由于序列是升序排列，所以区间[Mid,Right]都可以被排除，修改右边界Right=Mid-1；
③如果a[Mid]<=x，修改左边界Left=Mid+1； 重复执行二分操作直到Left>Right。
下面我们来分析答案的情况。循环结束示意图如下：
最终循环结束时一定是Left=Right+1，根据二分第②步的做法我们知道Right的右边一定都是大于x的，而根据第③步我们可以知道Left左边一定是小于等于x的。
所以，一目了然，最终答案是Right指向的数。Right=0就是题目中输出-1的情况。
参考代码
#include <bits/stdc++.h>
using namespace std;
int n,m,a[100005];
int main(){
scanf("%d %d",&n,&m);
for (int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
a[0]=-1;
for(int i=1;i<=m;i++){
int x;
int left=1,right=n,mid;
scanf("%d",&x);
while(left<=right){//进行二分
mid = (left + right) / 2;
if (a[mid] <= x){
left = mid + 1;
} else {
right = mid - 1;
}
}
printf("%d\n",a[right]);
}
return 0;
}