输入：一个有序数组A（所有元素都是整数，并且以递增顺序不同）和c（整数）
输出：返回随机选择的索引，以使该索引满足要求：|A[i]-i| <= c
在最坏的情况下，它应该在O（logN）时间内运行。
[我最初的想法是对索引i进行二进制搜索，以使A[i] = 0或壁橱为0。然后，该索引将数组分为2部分。
左侧部分包含元素<0，右侧部分包含元素> 0。
在右侧，运行类似于二进制搜索的算法以检查中间值，并查看是否为A[mid]-mid <=c，如果是，请转到[mid+1, end]。但是，当我有以下示例时，我发现了此问题：
c=2
i 0 1 2 3 4 5 6 7
A[i] -5 -4 -1 0 1 5 8 9
A[4]不符合|A[4]-4| <=2，但它将包含在我的算法中。所以我现在完全不知道这个问题...
让我们看一下数据。它从A开始，其中包含不同的排序整数，对于任何一对连续元素，A[i] <= A[i + 1] - 1。
这些元素的搜索键是A[i] - i和A[i + 1] - i - 1。从不等式的两边减去i表示两个连续的键，如果相等，则相等或增加，如果负，则相等或递减。
如果问题不要求绝对值，则解决起来很简单。您只需要检查第一个元素，或者它符合那里的标准，否则就没有元素。
绝对值表示您的琴键可以减小，增大或稳定。减小的区域始终位于最小值的左侧，而增大的区域始终位于右侧。
您可以在log(N)时间内找到最小值，类似于二进制搜索，但是要从两端开始。诀窍是找出中点的哪一侧最小。
[从数组的两端和中心开始。为每个一半选择一个中点。如果中点小于中心，则最小值在该一半内：将边界调整为恰好一半，然后继续。如果不是，那就是那一半的新端点。您最多将执行2 * log(N/2) = O(log(N))操作。
您可以在边界最大相差1时开始提早终止，或者您早早满足了条件的元素。
如果您确实确实需要一个随机元素，而不是一个任意元素，则需要在每一半中搜索满足条件的边界。自O(4 log(N/2)) = O(log(N))起，这不会增加复杂性。大概从该间隔中选择一个随机数是O(1)。
如有必要，我将最后一部分留给读者练习。