通过使用稍微修改的二进制搜索，可以在O(logN)时间和O(1)空间上完成此操作。
考虑一个新的数组Y，这样Y[i] = X[i] - i
Array X : -3 -1 0 3 5 7
index : 0 1 2 3 4 5
Array Y : -3 -2 -2 0 1 2
由于元件在X处于 增加 顺序，新的数组中的元素Y将在 非递减 顺序。因此，对in 进行 将给出答案。0``Y
但是创造Y将需要时间O(N)和空间O(N)。因此，您无需修改??新的数组，只需修改二进制搜索，以Y[i]替换对的引用X[i] - i。
算法：
function (array X)
low = 0
high = (num of elements in X) - 1
while(low <= high)
mid = (low + high) / 2
// change X[mid] to X[mid] - mid
if(X[mid] - mid == 0)
return mid
// change here too
else if(X[mid] - mid < 0)
low = mid + 1;
else
high = mid - 1;
end while
return -1 // no such index exists...return an invalid index.
end function
602392714
清零编程群