在检查array [i] == i(必须是O(log n))时返回bool的递归算法

Question

我正在尝试编写递归算法,如果至少有一个则返回true array[i] == i.如果没有,则为假array[i] = i.

此外,所需的参数是(int * arr, int start, int end).所以我将用指针遍历数组.例如:

int A[] = {-50,-10,0,1,3,5,8,10};
cout << sameIndex(A,0,7) << endl; //displays 1 (true) since A[5] == 5

我遇到很多麻烦的部分是O(log n).我无法看到将数组划分为2的位置,每个函数调用都将获得正确的解决方案.试图提出这种算法的结构是我的头脑.有人能指出我正确的方向吗？我不是在寻找答案,我只是不知道如何以递归方式开始解决这个问题,更不用说在O(log n)时间内.

忘记提及是的整数是不同的和排序的.

我想到了!长颈鹿和亨里克船长是正确的,但他们使用略有不同的方法.我选择使用长颈鹿队长的方法,因为使用二分搜索会更简单,更直观.Henrik使用一个"技巧"来找到解决方案,通过减去array[i] - i检查它们是否等于0.无论如何,这里是解决方案:

bool sameIndex(int * A, int start, int end)
{
    int mid = (start + end)/2;

    if(start <= end)
    {
        if(*(A + mid) == mid)
            return true;
        else if(*(A + mid) > mid)                   //search left
            return sameIndex(A, start, mid - 1);
        else                                        //search right
            return sameIndex(A, mid + 1, end);
    }
    return false;
}

我让它变得比实际更难.

Answer 1

使用(array[i] == i)条件进行常规二进制搜索,而不是搜索特定值.

If (array[i] > i)
   move left
else
   move right

当然这需要对值进行排序,但是您的示例表明情况就是这样.