使用Divide and Conquer检查Sorted Array是否有A [i] = i

Question

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

返回 true if A[i] = i

else return false;

我要求只返回真或假,而不是立场.

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

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即使已经找到中间也会到达.

我应该做出哪些改变,以便在所有情况下都返回true.

Answer 1

在递归调用find的地方,你应该在调用find之前返回一个返回,这样它就会返回嵌套调用的结果

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