Рекурсивный троичный поиск в Java: разделите массив на три части и выполните рекурсивный поиск по заданному элементу.

Question

Я пытаюсь реализовать троичный поиск в массиве 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));
}

}

Answer 1

хорошо, так что я знаю, что эта проблема старая. Но я хотел бы опубликовать ответ для будущих людей, которые ищут это. Ваш код делает странные вещи с третьим. также в ваших заявлениях 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!!");
    }

}

Answer 2

Похоже, вы не правильно уменьшаете / увеличиваете границы. Например, при первом обращении к верхней трети вы проверяете, больше ли x значения в позиции high- (thirdile-1), которая является индексом 6. Но вы передаете в качестве индекса для минимума значение 5, когда вы должны передать значение 7 для минимума. Это может привести к тому, что на самом деле никогда не будет выделено значение в верхней трети ... Я думаю, что есть аналогичная ошибка в нижней и средней части.