特定の要素の Java 配列に三項検索を実装しようとしています。この時点で、配列の下位 3 分の 1 と上位 3 分の 1 で StackOverflowError が発生し、中央の 3 分の 1 で誤った結果が得られます。大変助かりました。
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));
}
}