一、二分查找的基本概念：
1、原理：
首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
2、二分查找的时间复杂度：
假设数据大小是n，每次查找后数据都会缩小为原来的一半，也就是会除以2。最坏情况下，直到查找区间被缩小为空，才停止。可以看出来，这是一个等比数列。其中n/2^k=1时， k的值就是总共缩小的次数。而每一次缩小操作只涉及两个数据的大小比较，所以，经过了k次区间缩小操作，时间复杂度就是O(k)。通过n/2^k=1，我们可以求得k=log2n，所以时间复杂度就是O(logn)。而对于链表来说，二分查找的时间复杂度就变成了O(n)。
二、二分查找的注意事项：
1、循环退出条件：
注意是low<=high，而不是low<high。
2、mid的取值：
mid=(low+high)/2这种写法是有问题的。因为如果low和high比较大的话，两者之和就有可能会溢出。改进的方法是将mid的计算方式写成low+(high-low)/2。更进一步，如果要将性能优化到极致的话，我们可以将这里的除以2操作转化成位运算low+((high-low)>>1)。因为相比除法运算来说，计算机处理位运算要快得多。
3、low和high的更新：
low=mid+1， high=mid-1。注意这里的+1和-1，如果直接写成low=mid或者high=mid，就可能会发生死循环。比如，当high=3， low=3时，如果a[3]不等于value，就会导致一直循环不退出。
三、二分查找的实现源码(Java)：
1、循环方式：
public static int BinarySearch(Integer[] srcArray, int des) {
//定义初始最小、最大索引
int start = 0;
int end = srcArray.length - 1;
//确保不会出现重复查找，越界
while (start <= end) {
//计算出中间索引值
int middle = start + ((end - start)>>1) ;//防止溢出
if (des == srcArray[middle]) {
return middle;
//判断下限
} else if (des < srcArray[middle]) {
end = middle - 1;
//判断上限
} else {
start = middle + 1;
}
}
//若没有，则返回-1
return -1;
}
2、递归方式：
public static int BinarySearch(int[] arr,int key,int low,int high){
if(key < arr[low] || key > arr[high] || low > high){
return -1;
}
int middle = low+((high-low)>>1); //初始中间位置
if(arr[middle] > key){
//比关键字大则关键字在左区域
return BinarySearch(arr, key, low, middle - 1);
}else if(arr[middle] < key){
//比关键字小则关键字在右区域
return BinarySearch(arr, key, middle + 1, high);
}else {
return middle;
}
}
四、二分查找的局限性：
1、二分查找依赖的是顺序表结构，简单点说就是数组。
2、二分查找针对的是有序数据。二分查找只能用在插入、删除操作不频繁，一次排序多次查找的场景中。
3、数据量太大不适合二分查找。二分查找的底层需要依赖数组这种数据结构，而数组为了支持随机访问的特性，要求内存空间连续，对内存的要求比较苛刻。比如，我们有1GB大小的数据，如果希望用数组来存储，那就需要1GB的连续内存空间。
