0

我正在尝试在给定元素的 java 数组中实现三元搜索。此时，我在数组的下三分之一和上三分之一处得到一个 StackOverflowError，在中间三分之一处得到一个不正确的结果。非常感谢帮助。

public class TernarySearch {

    static int[] ints = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

    public static int search(int[] a, int x, int low, int high) {
    // int mid = (high + low) / 2;
    int thirdile = a.length / 3;
//  System.out.println(a.length/3);
//  System.out.println(thirdile);

    if (low > high) {
        System.out.println("low is greater than high. Item not found.");
        return 0;

    } else if (x > a[(high-(thirdile - 1))]) { // upper third
        System.out.println("X is greater than mid. higher third.");
        return search(a, x, (high - thirdile), high);
    } else if (x > a[thirdile - 1] && x < (high -thirdile)) { // middle third
        System.out.println("X is in the middle third.");
        return search(a, x, thirdile + 1, (high - thirdile) - 1);

    } else if (x < a[thirdile -1 ]) { // lower third
        System.out.println("X is less than thirdile. lower third.");
        return search(a, x, low, thirdile);
    }
    else {
        System.out.println("Found it at first thirdile");
        return thirdile;
    }

}

public static void main(String[] args) {

    System.out.println(search(ints, 2, 0, ints.length - 1));
}

}

4

2 回答 2

0

似乎您没有正确减少/增加界限。例如，第一次调用前三分之一时，您正在检查 x 是否大于位置 high-(thirdile - 1) 的值，即索引 6。但是您将值 5 作为低值的索引传递，当您应该将值 7 传递给低点时。这可能导致永远无法真正隔离前三分之一的值......我想在低端和中端也有类似的错误。

于 2011-11-29T06:13:34.100 回答
0

好的，所以我知道这个问题很老了。但我想我会为未来正在寻找这个的人发布一个答案。您的代码对三分位数做了一些奇怪的事情。在您的 if 语句中也不包括所有内容。你错过了不同的 -1 或者你不应该有 -1 。同样在您的递归调用中，您并不总是将低或高更改为应有的值。希望这段代码能帮助人们

public class TernarySearch {  
    static int[] ints = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

    public static int search(int[] a, int key, int low, int high) {
        // int mid = (high + low) / 2;
        //int thirdile = (high + low)/3
        int firstThird = ((high+1)-low)/3;
        int secondThird = ((2*((high+1)-1))/3);
        //  System.out.println(a.length/3);
        //  System.out.println(thirdile);

        if (low > high) {
            System.out.println("low is greater than high."+ key +" not found.");
            return -1;

        } else if (key > a[secondThird]) { // upper third
            System.out.println("key is greater than secondThird. its in higher third.");
            return search(a, key, secondThird+1, high);
        } else if (key > a[firstThird]) { // middle third
            System.out.println("key is in the middle third.");
            return search(a, key, firstThird+1, secondThird);
            // high is secondThird, because it could be equal to the secondThird still
            // all we know is that it wasn't higher than a[secondThird], but was higher
            //than a[firstThird]
        } else if (key < a[firstThird]) { // lower third
            System.out.println("key is less than thirdile. lower third.");
            return search(a, key, low, firstThird-1);
        }
        else {
            System.out.println("Found it at first third at index: "+firstThird);
            return firstThird;
        }

    }

    public static void main(String[] args) {

        System.out.println(search(ints, 2, 0, ints.length - 1));//print out the index number that is returned
        //if it is -1 that is printed out, 2 wasn't found, else it was found
        int myKeyIndex = search(ints, 2, 0, ints.length-1);
        if(myKeyIndex != -1)
            System.out.println(ints[myKeyIndex]+ "was found in the array!!");
        else
            System.out.println("Didn't find the key!!");
    }

}
于 2014-04-03T02:52:10.487 回答