http://katemats.com/interview-questions/二進制搜索算法的說：性能時，有很多重複
給你一個有序數組，你想盡快找到你怎麼做搜索的數量N. （不只是遍歷每個元素）？
- 如果數組中有大量重複項，算法的性能如何改變？
我的回答第一個問題是二進制搜索，這是O（的log（n）），其中n是陣列中元件的數量。
根據this answer，「在」元素K在A中不存在且小於A中的所有元素「的最壞情況下，」我們有最大log_2（n-1）個步驟「。
我認爲第二個問題的答案是它不會影響性能。它是否正確？
我不認爲有重複的事情。
你正在尋找一個特定數量N，重要的是當前節點是否匹配N.
如果我期待在列表中的號碼1 1-2-3-4- 5-6的表現與搜索1-9-9-9-9-9列表相同。
如果數字N重複，那麼您將有機會盡快找到它的幾個步驟。例如，如果在列表1-1-1-1-1-9上進行了相同的搜索。
如果你說的是最壞情況/大O，那麼你是正確的 - log（n）是你的約束。但是，如果您的數據分佈相當均勻（或者您可以映射到該分佈），那麼插入分區的位置可以獲得日誌（log（n））行爲。當你進行插值的時候，你也可以擺脫你在尋找最終元素之一的情況下的糟糕情況（當然，儘管有新的病理情況）。
對於許多許多重複項目，您可能願意在下一個探測器上進一步邁進直接中心。隨着更多的嘟，，你有更好的猜測正確的邊緣。雖然總是選擇中途點在適當的時間讓你在那裏，但受過教育的猜測可能會給你一些非常出色的平均表現。
當我面試時，我喜歡聽到這些答案，既有關於本書的知識，又有什麼理論，還有什麼事情可以做，以專注於給定的情況。通常這些常量因素可能會非常有用（請參閱快速排序及其分區選擇方案）。