首页 文章

使用递归方法进行三叉搜索

提问于
浏览 次
2

我正在编写一种递归方法，它不是执行二进制搜索算法，而是将数组拆分为三个并使用三元搜索算法 . 我相当肯定我的递归情况是正确的，但我的基本情况似乎有问题 . 如果数组包含两个或更少的值，那么基本情况应该是非递归检查，如果该值在数组中并返回索引 . 如果找不到该值，则返回-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 . 这个方法有什么问题，或者我只是设置我的测试代码错了？

java arrays algorithm recursion

3 回答

  • 0

    你似乎在混淆 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的数组 .

    回复于
  • 1

    我想你不明白Heuster的回答 . 这就是我要做的事情，在我看来Heuster说的是这样的：

    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);
            } else if (x < array[secondThird]) {
                return trinarySearch(array, x, firstThird, secondThird);
            } else { // must be (x > array[secondThird])
                return trinarySearch(array, x, secondThird, high);
            }
        }
    }
    回复于
  • 0

    你错过了递归部分的一个重要条件 if(x==splitingIndex)

    我已经改变了你的代码和它的工作
    查看更改

    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 firstThird;
        }
        else if (x < array[firstThird]) {
            return trinarySearch(array, x, low, firstThird - 1);
        }

        if(x == array[secondThird])
        {
            return secondThird;
        }
        else if (x < array[secondThird]) {
            return trinarySearch(array, x, firstThird + 1, secondThird - 1);
        }



            return trinarySearch(array, x, secondThird + 1, high);
        }
    }
    回复于

相关问题