mid = (low + high) / 2 来自 mid = low + (high - low) / 2 的不同答案

Question

我正在研究二进制搜索和插入的代码。

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

我发现我计算 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) 与 (int) 1.0 + (int)(-1.0 / 2.0)

mid = (low + high) / 2 来自 mid = low + (high - low) / 2 的不同答案

mid = (low + high) / 2 different answer from mid = low + (high - low) / 2

java

arrays