我正在尋找一種類似于二進制搜索的演算法，但它適用于本質上是回圈的資料結構，例如回圈緩沖區。我正在處理一個非常復雜的問題，但我能夠將其剝離，因此更容易描述（并且我希望更容易找到解決方案）。
假設我們有一個兩端相連的數字陣列和一個可以向前和向后移動并可以從陣列中獲取值的視圖視窗（它類似于可以向前和向后移動的 C 迭代器）。陣列中的值之一為零，這是我們想要找到的“甜蜜點”。
我們對陣列中的值的了解是：
- 它們是排序的，這意味著當我們向前移動視窗時，數字會增加（反之亦然），
- 它們不是均勻間隔的：例如，如果我們讀“16”，這并不意味著如果我們向后移動 16 個元素，我們就會達到零，
- 最后但并非最不重要的一點：陣列中有一個點，在該點之前，值是正值，但在那之后它們被“翻轉”并從負值開始（就像我們將它們添加到一個整數變數，直到計數器出現）
最后一個是我解決二分搜索問題的第一種方法失敗的地方。另外，如果我可以補充一下，讀取值操作很昂貴，所以越少越好。
PS：我正在尋找 C 代碼，但如果您了解 C#、Java、JavaScript 或 Python 并且喜歡用其中一種語言撰寫演算法，那么這沒問題:)。
uj5u.com熱心網友回復：
如果我理解正確，你有一個隨機訪問的陣列（如果只允許順序訪問，問題就微不足道了；那個“視窗”概念似乎不相關），持有一個正數然后負數的序列，中間有一個零，但是這個序列是任意旋轉的。（將陣列視為環形緩沖區只會掩蓋推理。）
因此，您有三個部分，帶有符號 - 或 - -，通過查看極端元素，您可以分辨出這兩種模式中的哪一種。
現在壞訊息是：沒有二分搜索可以作業，因為無論您對陣列進行采樣的順序如何，您總是可以找到相同符號的元素，除了最后（在相反符號的單個元素的極端情況下）。
這與對應于 - 或 - 模式的標準二分情況形成對比：擊中相同符號的兩個元素允許您丟棄中間的整個部分。
如果已知正負子序列的長度至少為 M，則通過對每個 M/2 元素進行采樣，您肯定會發現符號發生變化，并且可以開始兩個二分法。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/353924.html
上一篇：雙鏈表未顯示我正在搜索的確切值
下一篇：將偏移分頁轉換為頁碼分頁的演算法