Java分而治之算法栈溢出错误

Question

我正在尝试使用分而治之法找出 int 数组中最小数字的索引，但出现堆栈溢出错误：

Exception in thread "main" java.lang.WhosebugError
    at java.lang.StrictMath.floor(Unknown Source)
    at java.lang.Math.floor(Unknown Source)

这是我的分而治之法：

private static int dC(int[] a, int f, int l) {
        if(f == 1)
            return f;
        if(a[dC(a, f, (int)(Math.floor((double)(f+l)/2)))] > a[dC(a, (int)(Math.floor((double)(f+l)/2)+1), l)])
            return dC(a, (int)(Math.floor((double)(f+l)/2)+1), l);
        else
            return dC(a, f, (int)(Math.floor((double)(f+l)/2)));
    }

这是我在主要方法中输入的内容：

int[] a = {35,30,40,50};

System.out.println(dC(a, 0, 3));

Answer 1

您的停止有问题"rule"

private static int dC(int[] a, int f, int l) {
        if(l == f) // <-- This mean you have one item, so you want to return it.
            return f;
        if(a[dC(a, f, (int)(Math.floor((double)(f+l)/2)))] > a[dC(a, (int)(Math.floor((double)(f+l)/2)+1), l)])
            return dC(a, (int)(Math.floor((double)(f+l)/2)+1), l);
        else
            return dC(a, f, (int)(Math.floor((double)(f+l)/2)));
    }

此外，我会尝试只进行一次计算，所以像这样（也是 Joop Eggen 所说的关于整数算法的内容）：

private static int dC(int[] a, int f, int l) {
        if(l == f)
            return f;
        int m = (f+l) / 2;
        int left = dC(a, f, m);
        int right = dC(a, m+1, l);
        if(a[left] > a[right])
            return left;
        else
            return right;
    }

Answer 2

这只是经典的二分查找问题。从我通过查看您的代码可以收集到的信息来看，您似乎陷入了用于对当前数组的左右子数组进行每次递归调用的逻辑。我在下面使用的逻辑是左递归从 start 到 (start+end)/2 的所有内容，右递归从 ((start+end)/2) + 1 到 end 的所有内容。这保证永远不会有任何重叠。

基本情况发生在算法发现自己位于数组中的单个条目上时。在这种情况下，我们只是 return 该值，我们不会进一步递归。

private static int dC(int[] a, int start, int end) {
    if (start == end) return a[start];

    int left = dC(a, start, (start+end)/2);
    int right = dC(a, ((start+end)/2) + 1, end);

    return left < right ? left : right;
}

public static void main(String args[])
{
    int[] a = {10, 3, 74, 0, 99, 9, 13};
    System.out.println(dC(a, 0, 6));   // prints 0
}

Demo

注意：我不知道 Math.floor 在这里扮演什么角色，因为您使用的是整数数字数组，而不是双精度数或浮点数。我删除了它，因为我认为不需要它。

Answer 3

将索引定位到 min/max 是一个典型的问题，您可以这样尝试：

public static void main(String... args) {
    int[] arr = generateArrays(100, 1000, 0, 10000, true);
    int minIndex = findMinIndex(arr, 1, arr.length - 1);
    int theMin = arr[minIndex];
    Arrays.sort(arr);
    System.out.println(String.format("The min located correctly: %s", arr[0] == theMin));
}

private static int findMinIndex(int[] a, int l, int r) {
    if (r - l < 1) return l;
    int mid = l + (r - l) / 2;
    int lIndex = findMinIndex(a, l + 1, mid);
    int rIndex = findMinIndex(a, mid + 1, r);
    int theMinIndex = l;
    if (a[lIndex] < a[theMinIndex]) theMinIndex = lIndex;
    if (a[rIndex] < a[theMinIndex]) theMinIndex = rIndex;
    return theMinIndex;
}

以及生成随机数组的助手。

public static int[] generateArrays(int minSize, int maxSize, int low, int high, boolean isUnique) {
    Random random = new Random(System.currentTimeMillis());
    int N = random.nextInt(maxSize - minSize + 1) + minSize;
    if (isUnique) {
        Set<Integer> intSet = new HashSet<>();
        while (intSet.size() < N) {
            intSet.add(random.nextInt(high - low) + low);
        }
        return intSet.stream().mapToInt(Integer::intValue).toArray();
    } else {
        int[] arr = new int[N];
        for (int i = 0; i < N; ++i) {
            arr[i] = random.nextInt(high - low) + low;
        }
        return arr;
    }
}

Java分而治之算法栈溢出错误

Java divide and conquer algorithm stack overflow error

java

stack-overflow

arrays

divide-and-conquer

Demo