首页 文章

使用递归进行二进制搜索

提问于
浏览
1
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 回答

  • 2

    关键是通过将修改后的 lowhigh 传递给下一个递归调用来更新 lowhigh 来更新搜索范围 . 每次调用,我们都会根据 inqarr[mid] 之间的比较将搜索范围更新为 [low, mid-1][mid+1, high]

    这将有效:

    public static int binarySearch(double[] arr, int low, int high, double inq){
        int mid = (low + high)/2;
        if(arr == null || low > high) return -1;
    
        if(arr[mid] == inq) return mid;
    
        if(arr[mid] < inq) { // inq is in the upper half
            return binarySearch(arr, mid+1, high, inq);
        }
        if(arr[mid] > inq) { // inq is in the lower half
            return binarySearch(arr, low, mid-1, inq);
        }
    }
    

相关问题