public static int binarySearch(double[] arr, int low, int high, double inq){
int mid = (low + high)/2;
if(arr == null) return -1;
if(low > high) return -1;
if(arr[(int)inq] < arr[low])
return -1;
if(arr[(int)inq] > arr[high])
return -1;
}
我想通过递归搜索数组arr来找到inq的索引 . 我只有终止案例 . 不知道如何解决这个问题 .
原来的问题是这个:
搜索数组切片 arr[low:high]
以查找inq的出现 . 如果inq出现在arr中,则返回索引i,使得 arr[i] == inq
. 否则,返回-1 . 假设arr按递增顺序排序 .
这些是一些案例的答案:
输入数组是table = {2,4,6,8,10,12,14} .
在表[0:6]的索引0处找到
-
2
-
3在表[0:6]中找到,索引为-1
-
4在表[2:6]中找到,索引为-1
-
12在表[2:5]的索引5处找到
我知道如何使用迭代来做到这一点,但我不熟悉递归方法 . 我对此表示感谢 .
1 回答
关键是通过将修改后的
low
和high
传递给下一个递归调用来更新low
和high
来更新搜索范围 . 每次调用,我们都会根据inq
和arr[mid]
之间的比较将搜索范围更新为[low, mid-1]
或[mid+1, high]
这将有效: