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

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得到的越多，得到的就越差。为了更好地理解，我推荐信息理论或微积分，它们对此有着有趣且互补的观点。