找到[我] =我在重复

有序数组给定整数数组排序与可能复制，你如何找到一个索引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-检查中间元素是否为答案的恒定时间）

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

来源

2017-03-04 Bugaboo

@HenkHolterman：如果'left' <0，那么算法会继续搜索。所以，最坏的情况是，它搜索数组的两侧，而不像典型的二进制搜索，只保证只查看数组的一半，对吧？ – Bugaboo

是的，它比一般的二进制搜索更有意义。我读了那部分错误。 –

除非您的注意力完全是最坏情况的行为，否则这比单纯的线性扫描更好，因为它通常可以以次线性方式执行。 – pjs

不，你不会错过任何东西。第一个分支存在短路，但最糟糕的情况是两个呼叫都会进行，这会导致线性时间复发。

事实上，这个问题没有一个简单的细胞探针下界的次线性时间算法。考虑阵列a其中

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

一些j的家庭。这些数组只能通过检查作为固定点的特定条目来区分，这意味着探针的下限。

我假设原来的CTCI问题不允许重复 - 那么修改后的数组a(i) - i是非递减的，允许二元搜索零元素。

来源

2017-03-04 19:05:25

是的，问题的原始版本只有不同的元素 – Bugaboo

找到[我] =我在重复

回答

相关问题