什么是二分查找?
二分查找（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 = mid - 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;
}
}
时间复杂度和空间复杂度
时间复杂度：
- 最坏的情况下两种方式时间复杂度一样：O(log2 N);
- 最好情况下为O(1);
空间复杂度：
算法的空间复杂度并不是计算实际占用的空间，而是计算整个算法的辅助空间单元的个数
- 非递归方式：由于辅助空间是常数级别的所以：空间复杂度是O(1);
- 递归方式：递归的次数和深度都是log2 N,每次所需要的辅助空间都是常数级别的：空间复杂度：O(log2N )。
二分查找中值(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)）的搜寻目标数。
问题
以上的二分查找解决不了如下几个问题：
变体一：查找第一个值等于给定值的元素
比如下面这样一个有序数组，其中，a[5]，a[6]，a[7] 的值都等于 8，是重复的数据。我们希望查找第一个等于 8 的数据，也就是下标是 5 的元素。
首先拿 8 与区间的中间值 a[4] 比较，8 比6 大，于是在下标 5 到 9 之间继续查找。下标 5 和 9 的中间位置是下标 7，a[7] 正好等于8，所以代码就返回了。尽管 a[7] 也等于 8，但它并不是我们想要找的第一个等于 8 的元素，因为第一个值等于 8的元素是数组下标为 5 的元素。
public class BinarySearch { public static void main(String[] args) { int[] array = { 5, 2, 10, 8, 7 }; // 使用Arrays.sort对数组进行排序，默认为升序。如果要实现降序，可以使用Arrays.sort(array, Comparator)实现自定义的排序 Arrays.sort(array); System.out.println(find(array, 10)); } public static int find(int[] a, int value) { int low = 0; int high = a.length - 1; //注意终止条件为low>high，因为low==high的这个元素有可能就是需要被查找的。 while (low <= high) { //这种写法主要为了防止(low+high)/2超过int的上限值 int mid = low + ((high - low) >> 1); //如果a[mid]>value，说明只能存在于[low~mid-1] if (a[mid] > value) { high = mid - 1; //同理若a[mid]<value，说明只能存在于[mid+1~high] } else if (a[mid] < value) { low = mid + 1; //这时候a[mid]==value，但是不一定是第一个等于value的 } else { //如果第一个元素等于value，很明显，那就返回第一个元素的地址。如果mid的前一个元素不等于value，直接返回，否则继续往前找 if ((mid == 0) || (a[mid - 1] != value)) { return mid; }else { //否则low不变，high往前移动一位，继续寻找 high = mid - 1; } } } return -1; } }
变体二：查找最后一个值等于给定值的元素
public class BinarySearch { public static void main(String[] args) { int[] array = { 5, 2, 10, 8, 7, 10 }; // 使用Arrays.sort对数组进行排序，默认为升序。如果要实现降序，可以使用Arrays.sort(array, Comparator)实现自定义的排序 Arrays.sort(array); System.out.println(find(array, 10)); } public static int find(int[] a, int value) { int low = 0; int high = a.length - 1; //注意终止条件为low>high，因为low==high的这个元素有可能就是需要被查找的。 while (low <= high) { //这种写法主要为了防止(low+high)/2超过int的上限值 int mid = low + ((high - low) >> 1); //如果a[mid]>value，说明只能存在于[low~mid-1] if (a[mid] > value) { high = mid - 1; //同理若a[mid]<value，说明只能存在于[mid+1~high] } else if (a[mid] < value) { low = mid + 1; //这时候a[mid]==value，但是不一定是第一个等于value的 } else { //如果最后一个元素等于value，很明显，那就返回最后一个元素的地址。如果mid的后一个元素不等于value，直接返回，否则继续往后找 if ((mid == a.length - 1) || (a[mid + 1] != value)) { return mid; }else { //否则high不变，low往前移动一位，继续寻找 low = mid + 1; } } } return -1; } }
变体三：查找第一个大于等于给定值的元素
在有序数组中，查找第一个大于等于给定值的元素。比如，数组中存储的这样一个序列：3，4，6，7，10。如果查找第一个大于等于 5 的元素，那就是 6。
public class BinarySearch { public static void main(String[] args) { int[] array = { 5, 2, 10, 8, 7, 10 }; // 使用Arrays.sort对数组进行排序，默认为升序。如果要实现降序，可以使用Arrays.sort(array, Comparator)实现自定义的排序 Arrays.sort(array); System.out.println(find(array, 6)); } public static int find(int[] a, int value) { int low = 0; int high = a.length - 1; while (low <= high) { int mid = low + ((high - low) >> 1); if (a[mid] >= value) { //第一个元素就比目标值大，那结果就是第一个元素。或者mid的前一个元素小于value，那此时mid就是那个元素 if (mid == 0 || a[mid - 1] < value) { return mid; }else { //否则将high往前移动一位，继续寻找 high = mid - 1; } } else { //如果a[mid]<value，那么元素只可能存在于[mid+1, high] low = mid + 1; } } return -1; } }
变体四：查找最后一个小于等于给定值的元素
查找最后一个小于等于给定值的元素。比如，数组中存储了这样一组数据：3，5，6，8，9，10。最后一个小于等于 7 的元素就是6。
public class BinarySearch { public static void main(String[] args) { int[] array = { 5, 2, 10, 8, 7, 10 }; // 使用Arrays.sort对数组进行排序，默认为升序。如果要实现降序，可以使用Arrays.sort(array, Comparator)实现自定义的排序 Arrays.sort(array); System.out.println(find(array, 6)); } public static int find(int[] a, int value) { int low = 0; int high = a.length - 1; while (low <= high) { int mid = low + ((high - low) >> 1); if (a[mid] > value) { // 将high往前移动一位，继续寻找 high = mid - 1; } else { //如果mid是最后一个元素，肯定就是他了。或者mid后面那个元素大于value，此时返回mid if ((mid == a.length - 1) || (a[mid + 1] > value)) { return mid; } else { //否则low继续后移 low = mid + 1; } } } return -1; } }
注：其实二分查找的重点就是在一轮没有查找到结果后，low以及high的值如何改变的问题