是否有比二分搜索中點更有效的搜索因子？

Question

天真的二進制搜索是一種非常有效的算法：在排序數組中獲取高點和低點的中點，並相應地調整高點或低點。然後你重新計算你的終點並迭代，直到你找到你的目標值（或者你當然不會）

現在很清楚，如果你不使用中點，那麼會給系統帶來一些風險。假設你將搜索目標從中點移開，並創建兩個方面 - 我稱它們爲大方和小方。 （這種轉變是朝向高還是低，因爲它會是對稱的。）風險是，如果你錯過了，你的搜索空間就會大於它：你必須搜索大的一面更大。但是，獎勵是，如果你的搜索空間更小。

它發生在我面前的風險與獎勵的空間數量是相同的，（沒有模式，我假設沒有），一個元素高於和低於中點的可能性是相等的。所以風險在於它落在新目標和中點之間。

現在，因爲空間數量影響搜索空間，並且搜索空間是按照對數方式測量的，所以在我看來，如果我使用了，比如我們的搜索空間是1/4和3/4，一半的小空間的日誌，其中大空間只增加了大約.6或.7。

因此，記住這一切：是否有更有效的方法來執行二進制搜索，而不僅僅是使用中點？

Answer 1

讓我們同意搜索關鍵字可能位於數組—的位置，否則，我們希望根據我們對位置的特殊知識設計算法。所以我們可以選擇的是每次拆分數組的位置。如果我們選擇一個數字0 < x < 1並將數組拆分，那麼左邊的機會是x，右邊的機會是1-x。在第一種情況下，我們將數組縮小x倍，第二種情況下縮小爲1-x。如果我們做了很多次這樣的事情，我們就會得到這些因素中的許多產品，所以這裏使用的「正確」的平均值就是幾何平均值。從這個意義上說，每步的平均減少量是x的權重x和1-x的權重1-x，總的x^x *（1-x）^（1-x）。

那麼這是什麼時候最小化？如果這是數學堆棧交換，我們將採用衍生物（使用產品規則，鏈式規則和指數規則），將它們設置爲零並解決。但是這是計算器，所以我們將其繪製爲：

你可以看到，你從1/2得到的越多，得到的就越差。爲了更好地理解，我推薦信息理論或微積分，它們對此有着有趣且互補的觀點。