详细分析二分查找算法

二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。

可以看出来，这是一个等比数列。其中 n/2k=1 时，k 的值就是总共缩小的次数。而每一次缩小操作只涉及两个数据的大小比较，所以，经过了 k 次区间缩小操作，时间复杂度就是 O(k)。通过 n/2k=1，我们可以求得 k=log2n，所以时间复杂度就是 O(logn)。

最简单的情况就是有序数组中不存在重复元素，我们在其中用二分查找值等于给定值的数据。

public int binarySearch(int[] array,int value){
	int low=0;
	int high=array.length-1;
	while(low<=high){
		int mid=low+((high-low)>>1);
		if(array[mid]<value){
			low=mid+1;
		}else if(array[mid]==value){
			return mid;
		}else{
			high=mid-1;
		}
	}
	return -1;
}

三个需要注意的地方：

一、循环退出的条件
注意是low<=high，而不是low<high；查找区间缩小至0查找元素，如若没有找到返回-1；

二、mid的取值

实际上，mid=(low+high)/2 这种写法是有问题的。因为如果 low 和 high 比较大的话，两者之和就有可能会溢出。改进的方法是将 mid 的计算方式写成 low+(high-low)/2。更进一步，如果要将性能优化到极致的话，我们可以将这里的除以 2 操作转化成位运算 low+((high-low)>>1)。因为相比除法运算来说，计算机处理位运算要快得多。

三、low和high的更新
low=mid+1，high=mid-1。注意这里的 +1 和 -1，如果直接写成 low=mid 或者 high=mid，就可能会发生死循环。比如，当 high=3，low=3 时，如果 a[3] 不等于 value，就会导致一直循环不退出。

二分查找的局限性：
二分查找虽然性能比较优秀，但应用场景也比较有限。底层必须依赖数组，并且还要求数据是有序的。对于较小规模的数据查找，我们直接使用顺序遍历就可以了，二分查找的优势并不明显。二分查找更适合处理静态数据，也就是没有频繁的数据插入、删除操作。

二分查找的变形：

1，查找第一个等于给定元素的值
有序数据集合中存在重复的数据，我们希望找到第一个值等于给定值的数据。

public int binarySearch(int[] array,int value){
	int low=0;
	int high=array.length-1;
	while(low<=high){
		int mid=low+((high-low)>>1);
		if(array[mid]<value){
			low=mid+1;
		}else if(array[mid]>value){
			high=mid-1;
		}else{
			if(mid==0||(array[mid-1]!=value)){
				return mid;
			}else{
				high=mid-1;
			}
		}
	}
	return -1;
}

这里当中间的值大于或小于value时，仍然按照正常处理；
当等于value时，我们就需要确认一下这个 a[mid] 是不是第一个值等于给定值的元素。如果 mid 等于 0，那这个元素已经是数组的第一个元素，那它肯定是我们要找的；如果 mid 不等于 0，但 a[mid] 的前一个元素 a[mid-1] 不等于 value，那也说明 a[mid] 就是我们要找的第一个值等于给定值的元素。

如果经过检查之后发现 a[mid] 前面的一个元素 a[mid-1] 也等于 value，那说明此时的 a[mid] 肯定不是我们要查找的第一个值等于给定值的元素。那我们就更新 high=mid-1，因为要找的元素肯定出现在 [low, mid-1] 之间。

2，查找最后一个等于给定值的元素

public int binarySearch(int[] array,int value){
	int low=0;
	int high=array.length-1;
	while(low<=high){
		int mid=low+((high-low)>>1);
		if(array[mid]<value){
			low=mid+1;
		}else if(array[mid]>value){
			high=mid-1;
		}else{
			if(mid==array.length-1||(array[mid+1]!=value)){
				return mid;
			}else{
				low=mid+1;
			}
		}
	}
	return -1;
}

如果 a[mid] 这个元素已经是数组中的最后一个元素了，那它肯定是我们要找的；如果 a[mid] 的后一个元素 a[mid+1] 不等于 value，那也说明 a[mid] 就是我们要找的最后一个值等于给定值的元素。
如果我们经过检查之后，发现 a[mid] 后面的一个元素 a[mid+1] 也等于 value，那说明当前的这个 a[mid] 并不是最后一个值等于给定值的元素。我们就更新 low=mid+1，因为要找的元素肯定出现在 [mid+1, high] 之间。

3，查找第一个大于等于给定值的元素
在有序数组中，查找第一个大于等于给定值的元素。比如，数组中存储的这样一个序列：3，4，6，7，10。如果查找第一个大于等于 5 的元素，那就是 6。

public int binarySearch(int[] array,int value){
	int low=0;
	int high=array.length-1;
	while(low<=high){
		int mid=low+((high-low)>>1);
		if(array[mid]>=value){
			if(mid==0||(array[mid-1]<value)){
				return mid;
			}else{
				high=mid-1;
			}
		}else{
			low=mid+1;
		}
	}
	return -1;
}

如果 a[mid] 小于要查找的值 value，那要查找的值肯定在 [mid+1, high] 之间，所以，我们更新 low=mid+1。

对于 a[mid] 大于等于给定值 value 的情况，我们要先看下这个 a[mid] 是不是我们要找的第一个值大于等于给定值的元素。如果 a[mid] 前面已经没有元素，或者前面一个元素小于要查找的值 value，那 a[mid] 就是我们要找的元素。这段逻辑对应的代码是第 7 行。

如果 a[mid-1] 也大于等于要查找的值 value，那说明要查找的元素在 [low, mid-1] 之间，所以，我们将 high 更新为 mid-1。

4，查找最后一个小于等于给定值的元素
比如，数组中存储了这样一组数据：3，5，6，8，9，10。最后一个小于等于 7 的元素就是 6。

public int binarySearch(int[] array,int value){
	int low=0;
	int high=array.length-1;
	while(low<=high){
		int mid=low+((high-low)>>1);
		if(array[mid]<=value){
			if(mid==array.length-1||(array[mid+1]>value)){
				return mid;
			}else{
				low=mid+1;
			}
		}else{
			high=mid-1;
		}
	}
	return -1;
}