Java 二分查找 并解决整数溢出

public class test {

    public static void main(String[] args) {
        int[] array = {12, 13, 14, 56, 78, 90, 100, 123, 150, 8848};
        int target = 100;
        Integer res = binarySearch(array, target);
        System.out.println(res);

    }

    static Integer binarySearch(int[] array, int target) {
        int l = 0, r = array.length, m = (l + r) >>> 1;
        while (l <= r) {
            if (target == array[m]) {
                return m;
            } else if (target < array[m]) {
                r = m - 1;
            } else if (target > array[m]) {
                l = m + 1;
            }
            m = (l + r) >>> 1;
        }
        return -1;
    }
}

对于超大型的整数(l+r)/2会出现整数溢出的情况，这时有两个解决方案：

方案一：

使用如上的方法“>>>”位运算不仅效率比普通算数运算效率高，而且不会出先溢出现象。

方法二：

修改计算方法： 因为(l+r)/2=l-l/2+r/2=l-(l-r)/2

所以将(l+r)/2改为l-(1-r)/2即可防止整数溢出，但效率会比位运算低一些，推荐用位运算。