虽然二分法很简单，但是之前并没有对其有过太多的注意，只是把它当成一个查找元素的方法来应用，但是随着后面做题的深入，发现二分法也有很多讲究，所以这里做一个总结归纳一下；
一、二分法的基础概念：二分法研究的序列可以分为重复或者非重复序列，其序列要求都是递增有序的；对于非重复序列，我们可以很简单的给出相应的推理和逻辑；例如，我们如果要在一个严格递增序列中查找给定的 x，就可以有以下代码：
int binarySearch(int A[],int left,int right,int x){
int mid;
while(left<=right){
mid=(left+right)/2;
if(A[mid]==x)
return mid;
else if(A[mid]>x){
right=mid-1;
}else{
left=mid+1;
}
}
return -1;
}
注意两点：1. 判定条件 left<=right, 有的情况下写成 left<right，这个需要视情况而定；2. 当 left 和 right 达到一定程度的时候，如果简单相加计算 mid 的时候，可能会导致溢出，所以往往比较保险的办法就是：
mid=left+(right-left)/2
这样就可以很好的避免溢出，从而保证能够进行 mid 的计算；
上述针对的是递增非重复序列，如果重复序列，我们又该作何思考？
例如示例中给出的问题，如果给出一个重复的递增序列 A，我们需要求出第一个大于等于 x 的位置 L 以及第一个大于 x 的元素的位置 R；这是两个小问题，首先先进行第一个小问题的求解：找出第一个大于等于 x 的位置 L；其实对于这个问题，前提就已经默认了，必有 L 存在，所以判定条件就会发生相应的变化；
int lower_bound(int A[],int left,int right,int x){
int mid;
while(left<right){
mid=(left+right)/2;
if(A[mid]>=x){
right=mid-1;
}else{
left=mid+1;
}
}
return left;
}
这里我们可以看出变了两个条件，第一个是 left<right，第二个是 A[mid]>=x；对于第一个条件的改变，我们可以理解为把符合条件的元素夹出来，当循环终止的时候，必有 left=right, 此时两个索引指向同一个元素，该元素就是我们在寻找的元素；而对于第二个条件的改变，则是由于题目性质决定的；如果中间点大于等于 x，则我们可以认为要寻找的第一个 x 在 mid 的左边，所以 right=mid。即使在等于条件下，由于 right=mid，所以还是可以保证要寻找的数在 [left,right] 区间内；这一点和之前的 mid+ 1 和 mid- 1 完全不同，其根本原因是序列内元素是否唯一；如果难以判别使用哪种方法，则每次及逆行 mid 迭代的时候，一定要试一试边界是否能够像预期那样包括进行需要寻找的元素；
第二个自问题就是求序列中第一个大于 x 的位置; 对于这个问题，我们仍然需要关注的是判定条件; 代码如下：
int upper_bound(int A[],int left,int right,int x){
int mid;
while(left<right){
mid=(left+right)/2;
if(A[mid]>x){
right=mid;
}else{
left=mid+1;
}
}
return left;
}
对于个算法，同样的我们需要 left==right 来将符合的值夹出来；当 A[mid]>x 时，由于我们寻找的时大于 x 的值，此时该值必在 mid 的左边，同样的，如果 mid 就是大于 x 的值，也应该包括进去，所以此时，right=mid; 当 A[mid]<= x 时，由于我们寻找的是一个大于 x 的值，所以 mid 不必包括进去，left=mid+1;
总的来说，上述推举的方法，都在解决一个核心问题：在该序列中，找到第一个符合该条件的值；
二、二分法的主要应用：1. 利用二分法求某数字的近似值：这个问题其实很经典，自己以前碰到过几次；
例如：求解根号 2 的近似值，要求精度在 10^-5；这个问题就可以利用该方法进行计算；首先我们需要构建目标函数 F(x)=x^2，从而转换成 1~2 区间内的实数计算；设置边界 left=1，right=2，来利用函数进行逼近；代码如下：
const double eps=1e-5;
double f(double x){
return x*x;
}
int binarySearch(){
double left=1;
double right=2;
double mid;
while(right-left>1e-5){
mid=(right+left)/2;
if(f(mid)>2){
right=mid;
}else{
left=mid;
}
}
return mid;
}
2. 快速幂：快速幂就是给出三个整数 a,b,m, 求得 a^b%m；这个问题也可以采用二分思想来进行递归计算；若 b 是奇数：a^b=a*a^(b-1)若 b 是偶数：a^b=a^(b/2)*a^(b/2); 代码如下：
long long binarypow(long long a,long long b,long long m){
if(b==0)
return 1;
if(b%2==1)
return a*binarypow(a,b-1,m)%m;
else{
long long mul=binarypow(a,b/2,m);
return mul*mul%m;
}
}
注意上述的 mul，不要单纯计算两次 a^(b/2), 而使用 mul，这样可以适当的介绍时间复杂度；