分而治之算法 - 二進制搜索變體

Question

這是理解分而治之算法的練習題。

給出一個N個排序整數的數組。除了一個 元素重複兩次以外，所有元素都是不同的。設計一個O（log N）算法來查找該元素。

我相信，我得到的數組需要被分割，看看是否在下一個索引中找到了相等的對應元素，這是二進制搜索的一些變體。但我找不到任何解決方案或指導。

Answer 1

你不能在O（log n）時間內完成它，因爲在任何步驟中，即使你把數組分成兩部分，你也不能決定哪個部分需要考慮進一步處理，哪些部分應該留下。 另一方面，如果連續數字都存在於數組中，那麼通過查看索引和索引中的值，我們可以確定重複數字是在數組的左側還是右側。