今天在編寫一些代碼時，我遇到了一個情況，這個情況導致我編寫了一種我以前從未見過的二進制搜索。這個二進制搜索有一個名稱，它真的是一個「二進制」搜索？這種二進制搜索是否有名字？

動機

首先，爲了使搜索更容易理解，我將解釋其催生創建使用情況。

假設您有一個有序號碼列表。系統會要求您查找最接近x的列表中的編號索引。

int findIndexClosestTo(int x);

的呼叫findIndexClosestTo()總是遵循這個規則：

如果findIndexClosestTo()最後的結果是i，然後指數接近i有幸成爲當前呼叫的結果概率較大findIndexClosestTo()。

換句話說，這次我們需要找到的索引更可能更接近我們發現的最後一個，而不是更遠。

例如，想象一個在屏幕上左右走動的模擬男孩。如果我們經常查詢男孩位置的指數，那麼他可能就在我們找到他的最後一個地方。

算法

鑑於以上的情況下，我們所知道的findIndexClosestTo()最後的結果是i（這實際上是第一次函數被調用，i默認列表的中間指標，爲簡單起見，儘管單獨的二進制搜索來查找第一個調用的結果實際上會更快），並且該函數已被再次調用。鑑於新號碼x，我們按照這個算法來尋找其索引：

interval = 1;
位於i我們正在尋找，x數？如果是這樣，請返回i;
如果不是，請確定x是高於還是低於i。（請記住，清單是排序的。）
移動interval指數的方向x。
如果我們在新位置找到了x，請返回該位置。
Double interval。（即interval *= 2）
如果我們已經通過x，回去interval指標，設定interval = 1，進入4

鑑於上述（動機標題下）的概率規則，這在我看來是找到正確索引的最有效方法。你知道更快的方法嗎？

來源

2011-08-26 Cory Klein

我認爲這實際上是一個數組而不是一個列表？因爲列表上的二進制搜索將是愚蠢的。 – Nemo

我會假設最好的答案將取決於基於i的位置的概率分佈是什麼。例如，如果有99％的可能性在我的3分之內，那麼與其他地方只有0.001％的可能性相比，非常不同的答案會很有用。我認爲最佳答案應該是基於概率的分佈，以便二分法搜索選擇一個點，使得每邊都有50％的機會。所以如果你可以定義概率曲線，你可以定義一個很好的算法。 – Chris

@Chris非常好點。如果所有數據點的概率都是相近的，那麼這可能會比常規二分查找更差。就我而言，從最後一點開始，概率似乎會呈指數衰減，在這種情況下，我相信這種搜索速度更快。它的插值是 –

你在做什麼的（恕我直言）版本的Interpolation search

在插值搜索你承擔數平均分配，那麼你嘗試從數組的第一個和最後一個數字和長度中猜測數字的位置。

對於您的情況，您正在修改interpolation-algo，以便您假定該鍵非常接近您搜索的最後一個數字。

另請注意，您的算法類似於算法TCP，它試圖找到最優的數據包大小。（不記得名字:(）

開始緩慢
1. 雙區間
2. 如果數據包無法重新從最後成功packet./從默認包大小。3重啓。

來源

2011-08-26 16:42:53

這是在談論我的頭頂，所以我沒有任何支持它，但直覺！

在步驟7，如果我們已經通過X，它可能會更快減半interval了，頭背對着x - 有效，interval = -(interval/2)，而不是重置interval爲1

我得素描儘管...

編輯：道歉 - 我在上面說無稽之談：不理我！（並且我將離開並且有一個正確這次考慮它...）

來源

2011-08-26 15:58:38 nihilogist

在最壞的情況下，您的算法是O（（log n）^ 2）。

假設你從0開始（有間隔= 1），並且你實際尋求值駐留在位置2^N - 1。

首先，將檢查1，2，4，8，... ，2 ^（n-1），2^n。哎呀，那是超調，所以回到2 ^（n-1）。（n-1）+1，2 ^（n-1）+2，...，2 ^（n-1）+ 2 ^（n-2），2 ^（（n-1）+2 ^（n-2） N-1）+ 2 ^（N-1）。最後一個詞是2^n，所以哎喲，再一次超過。回到2 ^（n-1）+ 2 ^（n-2）。

依此類推，直到最後達到2 ^（N-1）+ 2 ^（N-2）+ ... + 1 == 2^N - 1.

第一過沖了日誌n個步驟。接下來花了（log n）-1步。下一個花了（log n） - 2個步驟。等等。所以，最糟糕的情況是，你花了1 + 2 + 3 + ... + log n == O（（log n）^ 2）個步驟。

一個更好的主意，我認爲是，當您第一次過調時切換到傳統的二進制搜索。這將保持算法的O（log n）最差情況性能，而當目標確實在附近時，趨於更快一些。

我不知道這個算法的名字，但我喜歡它。（通過一個奇怪的巧合，我能參加昨天用它，真的。）

來源

2011-08-26 16:14:39 Nemo

。如果你正在處理一個大數組（n> 1024），插值通常會比二進制更好。對於n> 10000，這將會更快更舒適。 –

你例程是典型的插值例程。如果用隨機數（〜標準二分查找）調用它，則不會損失太多，但如果用緩慢增加的數字調用它，則不需要很長時間就可以找到正確的索引。

因此，這是一個合理的默認行爲，用於搜索有序表格以進行插值。

這個方法在Numerical Recipes第3版第3.1節中有很長的討論。

來源

2011-08-27 08:35:59

這種二進制搜索是否有名字？

動機

算法

回答

相關問題