递归二叉搜索数组出索引

Question

public static void main(String[] args) {
int [] arr = {11,14,18,22,36,89,125};
System.out.println(recursive_binary_search(arr,0,arr.length,989));
}

public static int recursive_binary_search(int[] A,int p,int r,int x) {
if( p > r) {
return -1;
}else {
int q=(p+r)/2;
if(A[q]==x) {
return q;
}else if(A[q]>x) {
return recursive_binary_search(A,p,q-1,x);
}else {
return recursive_binary_search(A,q+1,r,x);
}

}

}

嘿，感谢您的阅读。我对这种递归二叉搜索方法有一些问题。当我尝试搜索不在数组中的内容时，java 给了我"线程 'main" java.lang.ArrayIndexOutOfBoundsException： 7 中的异常"。

我认为它应该返回 -1，因为 p>r 条件。我试图将条件更改为 p>=r，但随后它会为数组中实际存在的东西返回 -1。我做错了什么？非常感谢

Answer 1

您的搜索应以0到arr.length-1开头，

System.out.println(recursive_binary_search(arr,0,arr.length-1,989));