在一個數組中找到2個峯

Question

我有一個數組，其順序類似於

增加，減少，增加，減少。

我想知道什麼是兩個局部最大元素在增加行爲的末尾。我知道我可以在O（n）時間找到他們，我想知道是否有可能在O（log n）時間或O（n）時間以上找到它。

Answer 1

如果你不知道你的數據遵循特定的模式 - 增加後減小再增大後減小的趨勢 - 那麼你可以做的最好的是O（n），因爲你將要研究每一個項目在數組中確定哪兩個最高點是。

如果你知道它肯定確實遵循這種模式，那麼我最好的猜測是二進制搜索的改編，肚裏大致爲：

• 挑數據集的中間點，選中「漸變「 - 兩個連續值之間的差異。
• 利用這個來劃分的數據在半套，再次檢查你的兩個新的空間的中間點;你希望以這種方式繼續細分，直到你發現你有足夠的數據點，然後按順序排列。在這兩個點之間是其中一個低谷，在第一個低點的左邊，最後一個點的右邊是你要找的高峯。
• 執行二進制搜索這兩個空間的找到實際的峯 - 再次，每次找到梯度檢查兩個值，而不是隻抽樣單值，所以你可以告訴保持其方向搜索

。

沒有做數學，我現成的，頂級的我頭的猜測是，這個算法是O（2log（n））的充其量爲O（n），在最壞的情況。這當然會是非常罕見的，它需要你只要搜索整個數據集，我覺得你需要一個平凡的小數據集比天真的搜索需要更長的時間。