一、二分法

二分法应用于具有单调性的一组数据的查找中，能够将复杂度由O(N)降低到O(logN)，实现方式简单，通过对比目标数组下表为mid处数值与查找值之间的大小关系以不断更新[left,right]的值，最终找到目标数。其中也包含着二叉树的思想，是不错的查找算法。

二分法可以使用递归实现，但在程序设计时更多采用非递归方式

tip：如果二分上界超过int型数据范围的一半，那么当欲查询元素在序列靠后的位置时可能会导致
mid=(left+right)/2这条语句溢出，因此考虑使用mid = left + (right-left)/2来替代

二、实现方式

# include<cstdio>//假设A[]单调递增
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;elseleft = mid+1;}return -1;
}

注意left<=right中的等于，因为倘若没有这个等于会漏掉一种情况下数据的对比，即mid== left == right的情况下A[mid]是否等于x。

三、问题拓展

1.2都是建立在单增条件下的查找

1.返回第一个大于等于x的元素位置

如果mid>=x，则直接返回
如果mid<x, 则将left增加为mid+1

# include<cstdio>//假设A[]单调递增
int binarySearch(int A[], int left, int right, int x){int mid;if(A[right]<x) //假设最大的都小于x，说明找不到return -1;while(left < right){mid = (left+right)/2;if(A[mid]>=x)right = mid;//往[left,mid]里寻找elseleft = mid+1;//往[mid+1,right]里寻找}return left;
}

2.返回第一个大于x的元素位置

int binarySearch(int A[], int left, int right, int x){int mid;if(A[right]<x) //假设最大的都小于x，说明找不到return -1;while(left < right){mid = (left+right)/2;if(A[mid]>x)//往[left,mid]寻找right = mid;else left = mid+1;//往[mid+1,right]寻找}return left;
}

进而我们能够推导出求返回特定元素的位置。

3.根号2近似值的计算

进一步对于任何单调函数我们都能够通过二分法逼近这个值。（三次根号，对数函数等等）

# include<cstdio>
# include<algorithm>
using namespace std;const double eps = 1e-6;
double f(double x){return x*x;
}int main()
{double mid,left=0,right=2;while((right-left)>eps){mid = (left+right)/2;if(f(mid)>2)right = mid;elseleft = mid;}printf("%lf",mid);
}

4.装水问题（方程解的逼近）

一侧面为半圆的储水装置，该半圆的半径为R，要求往里面装入高位h的水，使其侧面看去的面积S1与半圆面积S2比例恰好为r，如上图所示，现给定R和r，求高度h。
显然，当h增大时，r一定增大，这是一个单调增的函数，满足使用二分法。

# include<cstdio>
# include<algorithm>
# include<cmath>
const double pi = acos(-1.0); //PI
const double eps = 1e-5; //精度到1e-5
using namespace std;double area(double height, double R)
{double alpha = 2*acos((R-height)/R);return alpha*R*R/2;
}double height(double R, double ratio)
{double S2 = pi*R*R/2, S1 = S2*ratio,left = 0,right = R,mid;while(right-left>eps){mid = (right+left)/2;if(area(mid,R)>S1)right = mid;elseleft = mid;}return mid;
}int main()
{double h = height(5.2,0.5);printf("%lf",h);
}