java - 使用递归方法进行三元搜索

Question

我正在编写一个递归方法，它不是执行二进制搜索算法，而是将一个数组分成三个并使用三元搜索算法。我相当肯定我的递归案例是正确的，但我的基本案例似乎有问题。基本情况是针对数组是否包含两个或更少的值而制定的，应该以非递归方式检查该值是否在数组中并返回索引。如果未找到该值，则返回 -1。

由于我无法弄清楚的原因，这个方法无论如何都会返回 -1。不管数组的大小，或者数组是否包含值。这是方法。

public static int trinarySearch(int[] array, int x, int low, int high) {

    if (high - low < 3) { //BASE CASE.
        for (int i = low; i < high; i++) {
            if (array[i] == x) {
                return i;
            }
        }
        return -1;
    } else { //RECURSIVE CASE.

        int firstThird = low + (high - low) / 3;
        int secondThird = low + 2 * (high - low) / 3;

        if (x <= array[firstThird]) {
            return trinarySearch(array, x, low, firstThird - 1);
        } else if (x <= array[secondThird]) {
            return trinarySearch(array, x, firstThird + 1, secondThird - 1);
        } else { // must be (x > array[secondThird])
            return trinarySearch(array, x, secondThird + 1, high);
        }
    }
}

在我的测试代码中，我只是将一个数组设置为 int[] array = {1, 2, .....}

假设我搜索 int 2，它在数组中。我在测试代码中设置了一个数组，并将该方法称为 trinarySearch(array, 2, 0, array.length-1)。每次都打印-1。是方法有问题，还是我只是设置了错误的测试代码？

Answer 1

您似乎混淆了 low 的逻辑和 high .通常，您会将要检查的子数组定义为从 low 开始。 (含)并结束于 high (独家)。

您使用 high包容性(正如我从您使用 array.length-1 的示例调用中了解到的那样)，但随后像这样循环

for (int i = low; i < high; i++) {

不访问array[high] .

快速修复是更改 <至 <=并且您的代码运行良好。但是，我会推荐使用标准定义(高独占)，因为它也简化了代码的其他部分:

• 您不需要任何容易出错的 +1或 -1索引修复(不要忘记在递归情况下将 <= 更改为 <)。
• high-low是被检查的子数组的大小，所以你可以使用 high-low <= 3这更清楚地表明您的基本情况可以处理长度不超过 3 的数组。