java 二分查找的注意事项

二分查找也是最简单的算法之一了。但是最近发现一般的写法会有问题。

public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while(left <= right){
            int mid = (left + right) / 2;
            if(nums[mid] == target){
                return mid;
            }else if(nums[mid] < target){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        return -1;
    }

注意第五行代码：

int mid = (left + right) / 2;

这里。left + right 是会溢出的。只要这个数组我们开的足够大，比如1100000000，就能重现这个问题，虽然这需要我们费点内存。因此正确的解法是：int mid = (low + high) >>> 1; 三个>，无符号位移的意思。