1、算法思想：
二分查找又称折半查找，它是一种效率较高的查找方法。
时间复杂度：O（nlogn）
二分算法步骤描述：
① 首先在有序序列中确定整个查找区间的中间位置 mid = （ low + high ）/ 2
② 用待查关键字值与中间位置的关键字值进行比较；
若相等，则查找成功
若大于，则在后（右）半个区域继续进行折半查找
若小于，则在前（左）半个区域继续进行折半查找
③ 对确定的缩小区域再按折半查找，重复上述步骤。
2、实现：
//非递归，效率比较高
public static int binaryquery(int a[],int low,int high,int key) {
if(low>high) return -1;
while(low<=high) {
int mid=low+(high-low)/2;
if(a[mid]>key) {
high = mid-1;
}
if(a[mid]<key) {
low = mid+1;
}
if(a[mid]==key) {
return mid;
}
}
return -1;
}
//递归，代码简洁
public static int binaryquery(int a[],int low,int high,int key) {
if(low>high) return -1;
int mid = low + (high-low)/2;
if(a[mid]>key) {
return binaryquery1(a, low, mid-1, key);
}
if(a[mid]<key) {
return binaryquery1(a, mid+1, high, key);
}
if(a[mid]==key) {
return mid;
}
return -1;
}
3、注意地方：
mid的计算
算法一： mid = (low + high) / 2
算法二： mid = low + (high – low)/2
乍看起来，算法一简洁，算法二提取之后，跟算法一没有什么区别。但是实际上，区别是存在的。算法一的做法，在极端情况下，(low + high)存在着溢出的风险，进而得到错误的mid结果，导致程序错误。而算法二能够保证计算出来的mid，一定大于low，小于high，不存在溢出的问题。如数据库二分查找，数据库的一个索引页面(大小一般是8k或者是16k)，能够存储的索引记录是有限的，因此肯定不会出现(low + high)溢出的风险。这也是为什么InnoDB中的中值，采用的就是算法一的实现。但是，作为一个严谨的程序设计人员，还是推荐使用算法二，将任何潜在的风险，扼杀于摇篮之中。
4、缺陷及优化：
（1）待排序列必须是有序的；
（2）只能是数组：查询快，增删插入删除慢
优化：使用二叉查找树，最好的平衡二叉树
借鉴博文：https://www.cnblogs.com/wxd0108/p/5465926.html
http://hedengcheng.com/?p=595