在沒有訪問完整數組的情況下，在n個元素範圍1到n的排序數組中找到缺失元素

Question

在Oracle訪談中詢問「在沒有訪問完整數組的情況下在n個元素範圍1到n的有序數組中找到缺失元素」。我想知道是否有一種方法可以在不訪問所有元素的情況下找到缺失的元素？只有一個元素丟失，沒有重複。如果這個問題有解決方案，Plz會幫助我。

Answer 1

你做了一個稍微定製的二進制搜索。你訪問n/2st元素並查看值。如果它小於n/2，則缺少的元素位於數組的下半部分。其他在上面。然後你在下半部分做同樣的事情。並繼續，直到你只有一種可能性。適用於在O（log（n））中隨機訪問的排序數組。