mid =(低+高)/2与mid =低+(高-低)/2的不同答案

Question

我在玩二进制搜索和插入的代码。

给定一个排序整数数组，它应该找到目标数的索引。如果它不存在，那么它应该返回如果插入它的位置的索引。

我发现计算mid的方式会导致我的代码以不同的方式工作。

我想知道mid = (low + high) / 2和mid = low + (high - low) / 2之间是否有什么区别。

输入示例:数组[1,3,5,6]，目标值为2。

    public static int searchInsert(int[] nums, int target) {
        int high = nums.length - 1;
        int low = 0;
        int mid = low + (high - low) / 2; // diff if use: (low + high) / 2
        
        for( ; low <= high ; ) {
            if(nums[mid] > target) {
                high = mid - 1;
            } else if(nums[mid] < target) {
                low = mid + 1;
            } else {
                return mid;
            }
            mid = low + (high - low) / 2;  // diff if use: (low + high) / 2

            System.out.println(low + (high - low) / 2 + ": " + high + " " + low);
            System.out.println(mid + " " + high + " " + low);
        }
        return mid;
    }

Answer 1

不同之处(与您的数字示例)是：

在一个点(最后一个循环迭代)中，有low = 1和high = 0。

在这种情况下，公式(low + high) / 2得到(1 + 0) / 2，这是1 / 2，计算结果为0 (整数算术)。

但是公式low + (high - low) / 2给出了1 + (0 - 1) / 2，这是1 + (-1 / 2)和进一步的1 + 0，因为-1 /2在整数算术中也是0。

如果您有浮点步骤，它将归结为(int) (1.0 / 2.0) vs. (int) 1.0 + (int)(-1.0 / 2.0)。