在昨天的采访中，我被问到以下问题：
考虑一个Java或C++数组，它已排序，并且其中没有两个元素是相同的。你怎么能最好地找到一个索引说，这样的元素在那个索引也是。那是。XiiX[i] = i
作为澄清，她还给了我一个例子：
Array X : -3 -1 0 3 5 7
index : 0 1 2 3 4 5
Answer is 3 as X[3] = 3.
我能想到的最好的是线性搜索。面试后，我虽然在这个问题上做了很多，但找不到更好的解决方案。我的论点是：具有必需属性的元素可以在数组中的任何位置。因此，它也可以在数组的最末尾，因此我们需要检查每个元素。
我只是想从这里的社区确认我是对的。请告诉我，我是对的:)
这可以通过使用稍微修改的二进制搜索在时间和空间上完成。O(logN)O(1)
考虑一个新数组，以便YY[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
由于 中的元素按递增顺序排列，因此新数组中的元素将按非递减顺序排列。因此，二进制搜索in将给出答案。XY0Y
但创造需要空间和时间。因此，您无需创建新数组，只需修改二进制搜索，以便将 对 的引用替换为 。YO(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
有一些更快的解决方案，平均O（log n）或在某些情况下O（log log n）而不是O（n）。有一个谷歌的“二进制搜索”和“插值搜索”，你可能会找到非常好的解释。
如果数组未排序，那么是的，元素在任何地方，你不能在O（n）下，但排序数组不是这种情况。
--
根据要求对插值搜索的一些解释：
虽然二进制搜索仅涉及比较“更大/不更大”的两个元素，但插值搜索也试图利用数值。关键是：你有一个从0到20000的排序值范围。你寻找300 - 二进制搜索将从范围的一半开始，在10000。插值搜索猜测 300 可能比 20000 更接近 0，因此它将首先检查元素 6000 而不是 10000。然后 - 如果它太高，递归到较低的子范围，并且它太低 - 递归到较高的子范围。
对于具有 +- 值均匀分布的大数组，插值搜索的行为应该比二进制搜索快得多 - 对其进行编码并亲自查看。此外，如果首先使用一个插值搜索步骤，然后使用一个二进制搜索步骤，依此类推，则效果最佳。
请注意，这是人类在字典中查找某些内容时直观地执行的操作。
