搜索數組中的不同數字，當所有其他數字相同時，可以使用分治法在O（logn）中完成

Question

可以說我們有一個非常大的數組，並且我們需要找到唯一不同的數字數組中，所有其他數字在數組中都是相同的，我們可以使用divide和conquer在O（log n）中找到它，就像mergeSort一樣，請提供一個實現。

Answer 1

除非該數組是特殊的，否則這不能以比O（n）更好的時間複雜度完成。有了你所給出的約束，即使你應用了一個算法，如分而治之，你必須至少訪問一次數組元素。

作爲分割陣列將是O（log n）的和進行比較2個元素時陣列被減少到2號將是O（1）

這被錯誤地放置。劃分數組不是O（log n）。二進制搜索在O（log n）中起作用的原因是因爲數組是按排序的，這樣，即使不查看它們具有的元素，也可以在每一步中丟棄數組的另一半，從而將數組的大小減半原來的問題。直覺上，你可以這樣認爲：即使你繼續把數組分成兩半，所形成的樹的葉子節點是n/2（考慮你比較葉子上的2個元素）。你將不得不做n/2比較，這導致O（n）的漸近複雜性。