天真的二进制搜索是一种非常有效的算法：您在排序数组中取高点和低点的中点并相应地调整高点或低点 . 然后重新计算终点并迭代，直到找到目标值（当然，你没有 . ）
现在，很明显，如果你不使用中点，你会给系统带来一些风险 . 假设你将你的搜索目标从中点移开，你创造了两个方面 - 我称之为大方和小方 . （无论转移是高还是低，都无关紧要，因为它会是对称的 . ）风险在于，如果你错过，你的搜索空间会比它更大：你必须搜索大方更大 . 但是奖励是，如果你的搜索空间更小，那么
在我看来，风险与奖励的空间数量是相同的，并且（没有模式，我假设没有模式）元素高于和低于中点的可能性是相等的 . 所以风险在于它落在新目标和中点之间 .
现在因为空格的数量影响搜索空间，并且搜索空间是以对数方式测量的，在我看来，如果我使用，让我们说1/4和3/4用于我们的搜索空间，我已经剪切了小的日志空间减半，大空间只增加了大约0.6或.7 .
所以考虑到这一点：有没有比使用中点更有效的方式来执行二进制搜索？
1 回答
让我们同意搜索键同样可能位于数组中的位置 - 否则，我们想要根据我们对位置的特殊知识设计算法 . 所以我们可以选择的是每次分割数组的位置 . 如果我们选择一个数字0 <x <1并在那里拆分数组，那么它在左边的可能性是x，它在右边的可能性是1-x . 在第一种情况下，我们将数组缩短x倍，在第二种情况下缩短1-x倍 . 如果我们多次这样做，我们会得到许多这些因素的乘积，因此这里使用的“正确”平均值是几何平均值 . 在该意义上，每步的平均减少量是x，权重x和1-x，权重1-x，总共x ^ x *（1-x）^（1-x） .
那么什么时候最小化？如果这是数学堆栈交换，我们将采用衍 生产环境 品（使用产品规则，链规则和指数规则），将它们设置为零，然后求解 . 但这是stackoverflow，所以我们将其绘制成图形：
你可以看到你从1/2获得的越远，你得到的越多 . 为了更好地理解，我推荐信息理论或微积分，对此有一些有趣和互补的观点 .