最基础的二分我们经常用来查找序列中的某个数，当然这要求这个序列是单调的。
常见的二分查找代码如下：
int binary(int a[],int low,int high,int x){ //查找是否有此元素 int mid; while(low<=high) { mid=(low+high)/2; if(a[mid]=x)return mid; else if(a[mid]>x)high=mid-1; else { low=mid+1; } } return -1; }
基础拓展
如果我们需要查找大于等于x的第一个数，利用二分的思想，将上面的代码小改一下就如下了
int binaryone(int a[],int low,int high,int x) //第一个大于等于x的元素 { int mid; while(low<high) { mid=(low+high)/2; if(a[mid]>=x)high= mid; else { low=mid+1; } } return low; }
可以发现判断条件那里做出了改变，因为不能排除这个数就是要找的数，所以high= mid。
如果再继续发问，找第一个大于x的数，只要把判断条件改为>x即可
所以二分推广过去直接把那里变成条件C，就可以得出第一个符合条件C的结果。
继而继续追问，如果要求最后一个满足条件C位置怎么办？可以求出第一个满足条件！C的元素的位置再减一就好。
实际上，上述程序没有考虑是否查找成功，只是可以增加一个上届n,对上界n处理即可。而事实上，算法文件里面也有under_bound(),upper_bound()分别与之对应。
快速幂
快速幂是一种简单而有效的小算法，它可以以O（logn）的时间复杂度计算乘方。快速幂不仅本身非常常见，而且后续很多算法也都会用到快速幂。
而快速幂也运用了二分法的思想：
如果求a的b次方，如果b是偶数，可以拆成两个b/2次方相乘，如果b是奇数，可以拆成a*a的（b-1）次方，如此二分，就可快速求幂。
#include <iostream> using namespace std; typedef long long LL; LL binarypow(LL a,LL b) //递归写法 { if(b==0)return 1; if(b&1)return a*binarypow(a,b-1); else{ LL c=binarypow(a,b/2); //注意这里用一个数来得到运算结果 return c*c; } } LL binarypowone(LL a,LL b){ //迭代写法 LL ans=1; while(b>0){ if(b&1){ ans=ans*a; } a=a*a; b>>=1; } return ans; } int main(){ printf("%d %d",binarypow(7,13),binarypowone(7,13)); return 0; }
