科普：

        第一篇二分搜索论文是 1946 年发表，然而第一个没有 bug 的二分查找法却是在 1962 年才出现，中间用了 16 年的时间。

定义

        在计算机科学中，二分查找（英语：binary search），也称折半搜索（英语：half-interval search）、对数搜索（英语：logarithmic search），是一种在有序数组中查找某一特定元素的搜索算法。

算法

        搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束。如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

如果让你写二分查找你可能会这么写：

public static int find(int[] a,int data) {
		int mid = 0;
		if(a!=null) {
			int min=0;
			int max=a.length;
			while(min<=max) {
				mid=(min+max)/2;
				if(data>a[mid]) {
					min=mid+1;
				}else if(data<a[mid]){
					max=mid-1;
				}else {
					return mid;
				}
			}
			return -1;
		}else {
			return -1;
		}
	}

上述代码哪里可能会出现bug?

答案是 mid=(min+max)/2;

原因是当min和max的值太大时可能会导致溢出，导致数组访问出错。

那么这么改进呢？一般做法是将加法变成减法，

public static int find(int[] a,int data) {
		int mid = 0;
		if(a!=null) {
			int min=0;
			int max=a.length;
			while(min<=max) {
				mid=min+(max-min)/2;
				if(data>a[mid]) {
					min=mid+1;
				}else if(data<a[mid]){
					max=mid-1;
				}else {
					return mid;
				}
			}
			return -1;
		}else {
			return -1;
		}
	}

min+(max-min)/2和(min+max)/2是等价的，但是min+(max-min)/2在计算过程中最大数值不会超过max

还有一种更高逼格的写法，也是官方二分搜索算法的实现：位运算

public static int find(int[] a,int data) {
		int mid = 0;
		if(a!=null) {
			int min=0;
			int max=a.length;
			while(min<=max) {
				mid=min+((max-min)>>>1);//无符号位运算的优先级较低
				if(data>a[mid]) {
					min=mid+1;
				}else if(data<a[mid]){
					max=mid-1;
				}else {
					return mid;
				}
			}
			return -1;
		}else {
			return -1;
		}
	}