使用分而治之检查排序数组是否有 A[i] = i

Question

我得到一个具有不同元素的排序数组。

Return true if A[i] = i

else return false;

我只需要 return 真或假，而不是位置。

我已经实现了代码，但是有一些小错误。

private static boolean find(int[] a, int low, int high) 
{
    System.out.println(Arrays.toString(a)+" "+low+ " "+high);
    if(low<=high)
    {
        int mid = (low+high)/2;

        if(mid==a[mid])
        {
            return true;
        }
        else if(a[mid]>mid)
        {
            find (a,low,mid-1);
        }
        else{
            find (a,mid+1,high);
        } 

    }

    return false;


}

我知道它到达 return false 即使它找到了中间。

我应该做哪些更改才能使它return在所有情况下都是正确的。

Answer 1

在递归调用 find 的地方，在调用 find 之前应该有一个 return，这样它将 return 嵌套调用的结果

return find(...) //etc..

Answer 2

你的代码有问题！！

检查测试用例 0：[1,1,2,3,4,5,6,7] 和测试用例 1 = [1,2,3,4,5,6,6] 您的代码适用于 testcase1 而不适用于 testcase0

因为对于 testcase1，mid 是 3 和 4 > 3 然后你跳过包含答案的 [5,6,6] !!!! 希望对你有帮助

使用分而治之检查排序数组是否有 A[i] = i

Check if Sorted Array has A[i] = i using Divide and Conquer

java

algorithm

divide-and-conquer