找到[我] =我在重複

有序數組給定整數數組排序與可能複製，你如何找到一個索引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

找到[我] =我在重複

回答

相關問題