考虑到与整数有序数组可能重复，你如何找到一个索引i，使得A[i]=i
这是我读过的一本编程书籍中的一个问题（破解代码面试）。解决方案概述如下：
public static int magicFast(int[] array, int start, int end) {
if (end < start || start < 0 || end >= array.length) {
return -1;
}
int midlndex = (start + end) / 2;
int midValue = array[midlndex];
if (midValue == midlndex) {
return midlndex;
}
/* Search left */
int leftlndex = Math.min(midlndex - 1, midValue);
int left = magicFast(array, start, leftlndex);
if (left >= 0) {
return left;
}
/* Search right */
int rightlndex = Math.max(midlndex + i, midValue);
int right = magicFast(array, rightlndex, end);
return right;
}
作者没有评论时间的复杂性。但是，这似乎是O（n）解决方案，因为我们需要查看“中间”点的两侧，这与数组元素不同的问题不同。递归关系为T（n）= 2T（n / 2）+ c（c-用于检查中间元素是否为答案的恒定时间）
那么，这比简单的线性扫描更好吗？为了实现线性时间效率，这似乎过于复杂。我在这里想念什么吗？
不，您什么都不丢失。第一个分支存在短路，但最坏的情况是将同时执行两个调用，从而导致线性时间重复发生。
实际上，通过简单的单元探针下界，此问题没有亚线性时间算法。考虑阵列家族a，其中
a(i) = i + 1 for i ≠ j
a(j) = j
对于一些j。这些阵列只能通过检查特定点（即固定点）来区分，这意味着n - 1探针的下限。
我假设的原始CTCI问题不允许重复-则修改后的数组a(i) - i不减少，这允许对零元素进行二进制搜索。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句