常规二分查找中遇到的问题

以前我们写二分查找的时候，是这么写的：

public static int binarySearch2(int []a,int target){
        int i=0,j=a.length-1;
        while(i<=j){
            int mid=(i+j)/2;
            if(a[mid]==target){
                return mid;
            }else if(a[mid]<target){
                i=mid+1;
            }else {
                j=mid-1;
            }
        }
        return -1;
    }

这么写，其实存在错误：

int mid=(i+j)/2;在i,j都比较小的时候没有问题，但是，一旦j值很大很大，逼近int型的边界限定的时候，如果a[mid]<target,i=mid+1,j不变，那么此时此刻i值变为int型边界限定的一半，那么i+j的和就超过了int型的边界限定了，那么（i+j）/2中先进行的i+j运算就会出错，那么得到的新mid值就有错。

正确写法：

public static int binarySearch2(int []a,int target){
        int i=0,j=a.length-1;
        while(i<=j){
            int mid=(i+j)>>>1;
            if(a[mid]==target){
                return mid;
            }else if(a[mid]<target){
                i=mid+1;
            }else {
                j=mid-1;
            }
        }
        return -1;
    }

可以看到，int mid=(i+j)/2;变成了int mid=(i+j)>>>1;

解释一下：

右移运算符>>>,运算结果正好能对应一个整数的二分之一值，这就正好能代替数学上的除2运算，但是比除2运算要快。

mid=(left+right)>>1相当于mid=(left+right)/2