为什么"int mid = (left - right)/2 + right"会导致栈溢出？

Question

今天写归并排序的代码，运行int mid = (left - right)/2 + right;遇到了Whosebug错误。但是当我使用 int mid = left + (right - left) / 2; 时一切都很好。我很困惑，因为他们两个的数学意义是一样的（如果不是，为什么？）。

我看过这个问题，但我不确定它是否能回答这个问题。 why left+(right-left)/2 will not overflow?

这是我的代码，很抱歉之前没有上传代码

import java.util.Arrays;

public class Solution {
    public static void main(String[] args) {
        int[] array = {3,5,1,2,4,8};
        int[] result = mergeSort(array);
        System.out.println(Arrays.toString(result));
    }

    public static int[] mergeSort(int[] array) {
        if (array == null || array.length <= 1) {
            return array;
        }
        int[] helper = new int[array.length];
        sort(array, helper, 0, array.length - 1);
        return array;
    }

    public static void sort(int[] array, int[] helper, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = (left - right)/2 + right;
        //int mid = left + (right - left) / 2;
        sort(array, helper, left, mid);
        sort(array, helper, mid + 1, right);

        combine(array, helper, left, mid, right);
    }

    public static void combine(int[] array, int[] helper, int left, int mid, int right) {
        for (int i = left; i <= right; i++) {
            helper[i] = array[i];
        }

        int leftIndex = left;
        int rightIndex = mid + 1;
        while (leftIndex <= mid && rightIndex <= right) {
            if (helper[leftIndex] <= helper[rightIndex]) {
                array[left] = helper[leftIndex];
                left++;
                leftIndex++;
            } else {
                array[left] = helper[rightIndex];
                left++;
                rightIndex++;
            }
        }

        while (leftIndex <= mid) {
            array[left] = helper[leftIndex];
            left++;
            leftIndex++;
        }
    }
}

Answer 1

作为你运行这个，迟早，很可能left会比right少一个——例如，可能left = 3和right = 4.

在这种情况下，(left - right) / 2 和 (right - left) / 2 都计算为 0，因为整数除法舍入为零。所以，如果你有

int mid = (left - right)/2 + right;
sort(array, helper, left, mid);

在您对 sort(array, helper, left, right) 的调用中，然后您将使用完全相同的值重复调用。这会导致无限递归 - a WhosebugError.

但是当你有

int mid = left + (right - left)/2;
sort(array, helper, left, mid);

然后你用不同的值重复调用，所以递归有机会结束。

Answer 2

最初，您有 left < right。当然还有 right - left > 0，还有 left + (right - left) = right（来自基础代数）。

因此 left + (right - left) / 2 <= right。所以不会发生溢出，因为操作的每一步都受到 right 值的限制。

为什么"int mid = (left - right)/2 + right"会导致栈溢出？

Why "int mid = (left - right)/2 + right" will cause stack overflow?

java

stack-overflow

arrays