二分查找（binary search）又叫折半查找，它是一种在有序数组中查找某一特定元素的搜索算法。
使用二分查找算法找出arrays数组中8的位置
int[] arrays = new int[] {2,8,12,18,20,25,30,37,41,49,61};
将有序数组分为三个部分，分别为中间值前（中间值数之前的一组数据），中间值和中间值后（中间值之后的一组数据）；将要查找的数与中间值的数相比较，等于则退出查找，小于则在中间值前进行比较，大于在在中间值后进行比较，依次递归，直至查找到对应的值为止；当要查找数据结构为偶数时，中间值mid应向下取整处理；上述arrays数组中间值为{25}，中间值前为{2,8,12,18,20}，中间值后为{30,37,41,49,61}。二分查找计算原理图，如下：
public class BinarySearch { public static void main(String[] args) { Integer[] array = {5, 2, 10, 8, 7}; //使用Arrays.sort对数组进行排序，默认为升序。如果要实现降序，可以使用Arrays.sort(array, Comparator)实现自定义的排序 Arrays.sort(array); System.out.println(find(array, 7)); } public static Boolean find(Integer[] array, Integer param) { int start = 0; int end = array.length - 1; int mid; while(start <= end) { //使用位运算是为了防止start+end溢出的情况 mid = (start + end) >> 1; if(array[mid] == param) { return true; } //注意start、end一定要取当前mid值的前一位或后一位，以免出现死循环，比如start为3，end为4，mid=(start+end)/2一直为3，出现死循环 if(array[mid] < param) { start = mid + 1; }else { end = ((start + mid) >> 1) - 1; } } return false; } }
public class Binarysearch {
public static int rank(int key,int[] a)
{
return rank(key,a,0,a.length-1);
}
public static int rank(int key,int[] a,int lo, int hi)
{
if(lo>hi)//左边界下标比有边界下标大，则不符合条件，
return -1;
int mid = lo+(hi-lo)/2;
if(key<a[mid])
rank( key,a,lo,mid-1);
else if(key>mid)
rank(key,a,mid+1,hi);
return mid;
}
}
算法的空间复杂度并不是计算实际占用的空间，而是计算整个算法的辅助空间单元的个数
二分查找中值(mid)计算 二分查找中值计算有两种方式：
int mid = (low + high) / 2;
int mid = low + (high - low) / 2;
上述两种算法看似第一种要简洁，第二种提取之后，跟第一种没有什么区别。但是实际上上述两种计算是有区别的，第一种的做法是在极端情况下计算的，(low + high)存在着溢出的风险，进而有可能得到错误的mid结果，导致程序错误；而第二种算法能够保证计算出来的mid值一定大于low、小于high，不存在溢出的问题。 针对第一种算法为了防止溢出问题，可以使用：int mid = (high + low) >>> 1; 解决此问题。
解决二分查找缺陷问题更好的方法是使用二叉查找树，最好自然是自平衡二叉查找树，既能高效的（O(n log n)）构建有序元素集合，又能如同二分查找法一样快速（O(log n)）的搜寻目标数。
原文：https://www.cnblogs.com/alimayun/p/12523700.html