在具有重复项的排序数组中查找A [i] = i

Question

考虑到与整数有序数组可能重复,你如何找到一个索引i,使得A[i]=i

这是我读过的一本编程书中的一个问题(Cracking the code interview).解决方案概述如下:

 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 - 检查中间元素是否为答案的恒定时间)

这比简单的线性扫描更好吗？这似乎过于复杂,只是为了实现线性时间效率.我在这里错过了什么吗？

Answer 1

不,你没有遗漏任何东西.第一个分支有一个短路,但最坏的情况是两次调用都会产生,这会导致线性时间重现.

事实上,这个问题没有通过简单的单元探测器下限的次线性时间算法.考虑阵列家族a,其中

a(i) = i + 1 for i ? j
a(j) = j

对于一些j.这些数组只能通过检查作为固定点的特定条目来区分,这意味着n - 1探测的下限.

我假设的原始CTCI问题不允许重复 - 然后修改的数组a(i) - i是非减少的,这允许二元搜索零元素.