使用递归的二进制搜索 [英] Binary Search using Recursion

问题描述

    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 的索引.我所拥有的只是解雇案件.不知道如何解决这个问题.

I am suppose to search through the array arr recursively to find the index of inq. All I have is the termination cases. Not sure how to go about this problem.

最初的问题是这个:

在数组切片arr[low:high]中搜索是否出现 的inq.如果inq出现在arr中，则返回一个索引i arr[i] == inq.否则，返回-1.假设arr按升序排序.

search the array slice arr[low:high] for an occurrence of inq. If inq occurs in arr, return an index i such that arr[i] == inq. Otherwise, return -1. Assume that arr is sorted in increasing order.

这些是某些情况的答案:

And these are the answers to some cases:

输入数组为table = {2、4、6、8、10、12、14}.

The input array is table = { 2, 4, 6, 8, 10, 12, 14 }.

在表[0:6]的索引0处找到
• 2
在表[0:6]的索引-1处找到
• 3
在表[2:6]的索引-1中找到了
• 4
• 12在表[2:5]的索引5中找到

• 2 was found in table[0:6] at index 0
• 3 was found in table[0:6] at index -1
• 4 was found in table[2:6] at index -1
• 12 was found in table[2:5] at index 5

我知道如何使用迭代来做到这一点，但是我对递归方法还是陌生的.感谢您的帮助.

I know how to do it using iterations, but I am new to recursive methods. I'd appreciate any help on this.

推荐答案

关键是通过将修改后的low和high传递到下一个递归调用中来更新low和high来更新搜索范围. .每次通话时，我们都会根据inq和arr[mid]

The key is to update the search range by updating low and high by passing the modified low and high into the next recursive call. Each call, we update the search range to either [low, mid-1] or [mid+1, high] depending on comparison between inq and arr[mid]

这将起作用:

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);
    }
}

这篇关于使用递归的二进制搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！