找到一個索引i，使得[I] = I

Question

可能重複：
Interview question - Search in sorted array X for index i such that X[i] = i

您與整數的排序後的數組和數組的長度給出。現在你必須找到一個索引i，例如a(i)=i。 如果索引被給出，我可以在o（logn）中完成，但是如果索引i沒有被提及，怎麼辦？

Answer 1

正如亞歷山大在評論中指出的，該指數的預知意味着它是O(1)，而不是O(log N)。

而且，除非有一些你不告訴我們的信息，你需要O(n)的時間來做到這一點沒有這種先見之明：

for x = 0 to len(a) - 1: 
    if a[x] = x: 
     return x 

---

澄清：原來的問題沒有說明該名單排序，這是後來添加。由於這使問題成爲this one的重複，因此您應該查看解決方案的答案。

這個答案將保留原樣，因爲沒有重複其他人的意思，並且它與未排序的情況相關。

Answer 2

根據給出的信息，您需要檢查值直到找到匹配項。最壞的情況（不匹配，或匹配在最後一個單元格中找到）是O（n）。 如果數組已經排序，則可以執行二進制搜索，即O（log n）。

您的聲明要麼是錯誤的，要麼是您遺漏了一些信息。