在具有重复项的排序数组中查找A [i] = i(Finding A[i]=i in a sorted array with duplicates)

 给定一个可能重复的整数排序数组，你如何找到一个索引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 - 检查中间元素是否为答案的恒定时间） 
 
 这比简单的线性扫描更好吗？ 这似乎过于复杂，只是为了实现线性时间效率。 我在这里错过了什么吗？ 

Given a sorted array of integers with possibly duplicates, how do you find an index i such that A[i]=i
 
This is a problem in one of the programming books I read (Cracking the code interview). The solution is outlined as follows:
 
 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;    
}
 
The author does not comment on the time complexity. However, this seems to be O(n) solution since we need to look at both sides of the 'mid' point unlike the problem where array elements are distinct. The recurrence relation being T(n) = 2T(n/2) + c (c - constant time to check if the middle element is the answer)
 
How is this better than a simple linear scan then? This seems overly complicated just to achieve linear time efficiency. Am I missing something here?

原文：https://stackoverflow.com/questions/42599946