基础—二分查找

基本概念

查找是作为编程一个比较基础的一个功能点，其中比较流行的就是二分查找，其核心思想就是在不断的缩小查找的范围，而且是以lgn的数量级，所以比较受欢迎

实现

对于二分查找我们需要做的一个核心点就是获取中间位置，一个的做法都是直接进行除法计算：

(low + high)/2

但是这里有一个比较麻烦的问题，假设这个high的值很大，超过了int类型的最大值，这个计算公示就会造成溢出问题。那么怎么解决这样一个问题呢。
我们利用数学公示进行一个拆分：

(low + high)/2 = low / 2 + high/2 = (high - low)/2 + low

其实这个还会造成溢出问题，那么最终极的解决办法是怎么处理呢，当然是带符号移位：

(high + low) >>> 1;

实现模版

具体的实现可以参考如下的代码：

public class BinarySearch{
    public int search(int[] array, int target){
        int low = 0;
        int high = array.length;
        //这里需要区分到底要不要进去的问题
        while(low < high){
            int mid = (low + high) >>> 1;
            if(array[mid] < target){
                low = mid+ 1;
            }else if(array[mid] > array[high]){
                high = mid -1;
            }else{
                return mid;
            }
        }
    }
}