这个问题问得特别到位——直觉上我们都觉得对半分效率最高，但要从数学上把这个结论坐实，确实需要拆解一下核心逻辑。我从递推分析和决策树两个角度给你证明：

一、用递推式分析最坏情况时间复杂度 #

首先，我们定义：假设每次把样本空间按比例 (a : (1-a)) 分割（(0 < a < 1)），最坏情况下每次都会进入更大的那一部分子空间（因为最坏情况就是运气最差，每次都要搜更大的区域）。设 T(n) 为搜索大小为n的空间所需的最多比较次数，那么递推关系是：

T(n) = 1 + T(max(a*n, (1-a)*n))
边界条件：T(1) = 1（找到元素需要1次比较，找不到的情况类似，不影响渐近分析）

我们可以通过迭代这个递推式，计算需要多少次迭代才能把空间缩小到1：
经过k次迭代后，剩余空间大小是 n * (max(a, 1-a))^k
当剩余空间≤1时停止，即：
n * (max(a, 1-a))^k ≤ 1

两边取以2为底的对数（方便和二分搜索对比）：
k * log₂(max(a, 1-a)) ≤ -log₂n

因为 max(a,1-a) ≥ 1/2（不管怎么分，总有一部分至少占一半），所以 log₂(max(a,1-a)) ≥ -1。我们的目标是让k尽可能小，也就是让右边的分母 -log₂(max(a, 1-a)) 尽可能大。

现在看这个分母的最大值：

• 当 a=1/2 时，max(a,1-a)=1/2，分母是 -log₂(1/2)=1，此时 k ≈ log₂n
• 当 a≠1/2 时，比如 a=1/3（1:3分割），max(a,1-a)=2/3，分母是 -log₂(2/3)=log₂(3/2)≈0.585，此时 k≈log₂n / 0.585≈1.71 * log₂n，比二分搜索的次数多了70%
• 再极端点，比如 a=1/4（1:4分割），max(a,1-a)=3/4，分母是 -log₂(3/4)=log₂(4/3)≈0.415，此时 k≈log₂n / 0.415≈2.41 * log₂n，效率更低

显然，只有当 a=1/2 时，分母取到最大值1，对应的k最小，也就是最坏情况下的比较次数最少。

二、用决策树视角验证 #

从决策树的角度看，二分搜索的过程对应一棵平衡二叉决策树：每个比较节点的左右子树高度差不超过1。对于n个元素的搜索问题，决策树的叶子节点数至少是 n+1（对应找到n个元素中的一个，或者找不到的情况）。

根据二叉树的性质，高度为h的二叉树最多有 2^h 个叶子节点。要覆盖 n+1 个叶子节点，树的高度至少是 ⌈log₂(n+1)⌉——而平衡二叉树的高度刚好等于这个下界。

如果用非对半分割的比例，比如1:3，对应的决策树是不平衡的：每次分割后，较大的子树高度会比小的子树高很多，最终整棵树的高度会超过 ⌈log₂(n+1)⌉，也就是说最坏情况下的比较次数会比二分搜索多。

总结 #

不管是从递推式的渐近分析，还是决策树的高度下界来看，只有当每次把样本空间对半分割时，最坏情况下的时间复杂度达到了理论最小值 Θ(log n)，而且常数因子也是最小的。其他分割比例都会导致最坏情况下的搜索次数增加，效率降低。

内容的提问来源于stack exchange，提问作者zd_