在數組中使用重複元素的二進制搜索

Question

我想知道如何使用二分查找來處理數組中的重複元素。例如，我有一個像1 1 1 2 2 3 3這樣的數組。並且我有興趣尋找最後一次出現的次數爲2.

根據之前閱讀過的帖子，我們可以先使用二進制搜索找到2，然後掃描相鄰的元素。這需要o（log（n）+ k）。所以最糟糕的情況是當k = n時。然後它需要O（n）時間。有什麼方法可以改善最糟糕的時間表現嗎？謝謝。

Answer 1

做一個二進制搜索2.5。換句話說，如果您要搜索的值是N，那麼您的代碼應該將其視爲N，因爲它太小，而N+1就像它太大。該算法的主要區別在於它不能幸運並且提早終止（當它找到該值時）。它必須一路跑到最後，當high和low指數是相等的。在這一點上，你所尋求的指數應該不會超過最後的high/low指數的1。

Answer 2

最簡單的方法是做一個上界二分搜索。這與您提到的二元搜索完全相同，除了不是試圖找到數字的第一個實例，它首先是數字的第一個實例，它比所提供的更大。它們之間的區別僅僅是將<轉換爲<=。

一旦你找到一個大於你的數字的第一個實例，退一步索引，然後看看那裏的值。如果它是2，那麼你找到了最後的2個。如果是其他的，那麼陣列中沒有2。