魔法陣指數時間/空間複雜

Question

我一直在尋找以下問題：

神奇指數：魔術的索引數組A[0...n-1]被定義爲一個指數i如A[i] = i。給定排序的非明顯整數數組，請編寫一個方法來查找存在的魔術索引。

這裏是我的解決方案：

static int magicNonDistinct(int[] array, int start, int end) { 
    if (end < start) return -1; 
    int mid = start + (end - start)/2; 
    if (mid < 0 || mid >= array.length) return -1; 

    int v = array[mid]; 
    if (v == mid) return mid; 

    int leftEnd = Math.min(v, mid - 1); 
    int leftRes = magicNonDistinct(array, start, leftEnd); 
    if (leftRes != -1) return leftRes; 

    int rightStart = Math.max(v, mid + 1); 
    int rightRes = magicNonDistinct(array, rightStart, end); 
    return rightRes; 
} 

它工作得很好，是從書破解代碼採訪第6版推薦的解決方案，解決8.3跟進（抱歉破壞）。

然而一個不同的陣列沒有魔索引上運行此時，它訪問的所有元素，產生運行爲O（n）的時間的最壞情況。

由於它是遞歸它需要O（n）的存儲器作爲最壞的情況。

該解決方案爲什麼會是最好只是遍歷數組了嗎？這個解決方案（我自己的）更好，我會爭辯：

static int magicNonDistinctV2(int[] array) { 
    for (int i = 0; i < array.length; ++i) { 
    int v = array[i]; 
    if (v == i) return v; 
    if (v >= array.length) return -1; 
    else if (v > i) i = v - 1; 
    } 

    return -1; 
} 

O（n）運行時間O（1）空間總是？

有人能得出初步算法更好的時間複雜度？我一直在考慮看它是否爲O（d），其中d是不同元素的數量，但是由於最小/最大值僅在一個方向上起作用，所以該情況也是錯誤的（考慮如果v = 5, mid = 4和該陣列全是五個）。

編輯：

好的人認爲我的香蕉，並儘快尖叫O（日誌（n））的，因爲他們看到的東西，看起來像二進制搜索。對不起，不清楚的人。

讓我們約在第一次發佈的代碼講我做（由鼎的解決方案）：

如果我們有一個數組看起來像這樣：[-1, 0, 1, 2, 3, 4, 5, 6, 7, 8]，實際上是一個數組看起來像這樣：大小n的[-1,...,n-2]，我們知道沒有可匹配的元素。但是 - 該算法將訪問所有元素，因爲元素不是唯一的。我敢，運行它，它不能像普通的二進制搜索那樣將搜索空間除以2。請告訴我我的推理有什麼問題。

Answer 1

不，在我看來，第一個解決方案是不是O（log n）的其他答案的狀態，實在是O（n）的最壞的情況下（在它仍然需要經過所有元素最壞的情況下，可以考慮對等如作者也提到的那樣，陣列移動了一個）。

它不是O（log n）的原因是因爲它需要在中間的兩邊進行搜索（二進制搜索只檢查中間的一邊，因此它是O（log n））。

它允許跳過項目，如果你幸運的話，但是你的第二個迭代解決方案如果不需要看它們也會跳過項目（因爲你知道在數組排序的範圍內不能有神奇的索引），所以在我認爲第二種解決方案更好（同樣的複雜性+迭代性，即更好的空間複雜性，並且沒有相對昂貴的遞歸調用）。

編輯：但是，當我再次考慮第一個解決方案時，它在另一側允許也可以「跳過倒退」，如果可能的話，迭代解決方案不允許 - 考慮例如像{-10， - 9，-8，-7，-6，-5} - 迭代解決方案需要檢查所有元素，因爲它從頭開始，值不允許向前跳躍，而當從中間開始時，算法可以完全跳過檢查前半部分，然後檢查後半部分的前半部分等。

Answer 2

看起來你錯誤地理解了所需解決方案的時間複雜性。最壞的情況不是O(n)，它是O(log(n))。這是因爲在每次傳球時你都會搜索下一次只有一半的陣列。

這裏是一個C++ example並檢查對於11個元件的整個陣列，它僅需要3檢查。

Answer 3

• 你是對的，最壞的情況是O（n）。您可能需要訪問陣列的所有元素。
• 只有一個原因是不是訪問數組元素[mid，end]，那是array[mid] > end（因爲在那種情況下，[mid，end]元素肯定沒有神奇指數）。
• 同樣，只有一個理由，不是訪問數組元素[開始，中旬]，那是當array[start] > mid。
• 所以，有一個希望，你可以可能不必訪問所有的元素。因此，這是一種可能起作用的優化。

因此，這二元樣方法似乎比線性迭代整個陣列上，但在最壞的情況下更好，你會打爲O（n）。

---

_{PS：我假設數組按升序排序。}