递归二进制搜索双有序数组

Question

给定一个包含 n 个不同数字的数组，这些数字从索引 0 严格递增到 m，并且从索引 m 严格递减到索引 n-1，我想用递归的方式找到数组中最大数的索引m。我的方法需要运行与 O(log n)

成比例

到目前为止，我想到了使用二进制搜索递归算法，我相信在给定的时间复杂度内确实运行，并得出以下结果；

/* 
 * @param inputArr     -> input array of numbers over which the reccursive method is called 
 * @param head   -> the first index of the array passed as argument
 * @param tail     -> the last index of the array passed as argument
 * @returns max    -> index for the maximum of the ascending sequence
 */
public static int largestNumber(int[] inputArr, int head, int tail) {
    //base cases for recursion to stop
    if(head==tail)
        return head;

    int midIndex = (tail + head)/2;
    
    // the maximum is at the mid index
    if(inputArr[midIndex] > inputArr[midIndex +1] && inputArr[midIndex] < inputArr[midIndex -1]) {
        return midIndex;
    } else {
        
        // the maximum is not at the mid index
        if (inputArr[midIndex+1] > inputArr[midIndex]) {
            return largestNumber(inputArr, midIndex+1, tail);
        } else {
            return largestNumber(inputArr, head, midIndex - 1);
        }
    }

这个的输出是

都是不正确的（从上到下应该是 0 , 3, 2, 4），表明我对基本情况或条件语句的处理不当。有没有人对我可能出错的地方或我遗漏的情况有任何暗示？在我看来我的功能似乎已经完成了...

Answer 1

我看到的一件事是您比较的是 inputArr[midIndex] > inputArr[midIndex - 1] 而 inputArr[midIndex] < inputArr[midIndex - 1]。为了return最大，你希望inputArr[midIndex]大于两边的元素。

当 head == 0 和 tail == 1 时，您也在访问非法数组索引。

递归二进制搜索双有序数组

Recursion binary search for a double-ordered array

java

recursion

binary-search