二分查找int溢出问题

二分查找时中间有一步操作就是求取中间值,一般写法为mid = (min + max) / 2,但是这种写法存在问题。原因:min可能不断增大,如果到极限状态,也就是min达到了max-1的地步的时候刚好数组的长度又很大,那么就可能导致min + max的溢出,所以需要改进。

改进一:mid = (max - min) / 2 + min;
改进二:((max - min) >>> 1) + min; 逼格更高
附上源码:

 public static int binary(int[] arr, int data) {
        int min = 0;
        int max = arr.length - 1;
        int mid;
        while (min <= max) {
            // 二分查找时这种写法,在数据量很大的时候可能会导致int类型溢出。
            // 原因:min可能不断增大,如果到极限状态,比如min达到了max-1的地步的时候
            // 刚好数组的长度又很大,那么就可能导致min + max的溢出,所以需要改进
            // mid = (min + max) / 2;
            // 这种写法就可以了,不过下面的逼格更高点
            // mid = (max - min) / 2 + min;
            // 无符号位运算符的优先级较低,所以括起来
            mid = ((max - min) >>> 1) + min;

            if (arr[mid] > data) {
                max = mid - 1;
            } else if (arr[mid] < data) {
                min = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。