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

Question

给定一个排序的整数数组，其中 可能重复 ，如何找到索引 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) 解决方案，因为我们需要查看 'mid' 点的两侧，这与数组元素不同的问题不同。递归关系为 T(n) = 2T(n/2) + c（c - 检查中间元素是否为答案的常数时间）

这比简单的线性扫描好在哪里？这似乎过于复杂，只是为了实现线性时间效率。我在这里遗漏了什么吗？

Answer 1

不，你没有遗漏任何东西。第一个分支有短路，但最坏的情况是两次调用都会进行，这会导致线性时间重复。

事实上，这个问题没有通过简单的细胞探测下界的亚线性时间算法。考虑数组族 a where

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

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

我假设的原始 CTCI 问题不允许重复——然后修改后的数组 a(i) - i 是非递减的，这允许二进制搜索零元素。

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

Finding A[i]=i in a sorted array with duplicates

arrays

algorithm

binary-search