二分查找的平均查找长度（ASL）是衡量其效率的重要指标，其计算方法如下：
一、平均查找长度公式
对于长度为 n 的有序表，二分查找的平均查找长度为： $$ ASL = \frac{\sum_{i=1}^{h} i \cdot 2^{i-1}}{n} $$
其中， h 是判定树的高度，满足 $n = 2^h - 1$，即 $h = \log_2（n+1）$。
二、推导过程
-
判定树结构
二分查找的判定树是平衡二叉树，其节点数与层数关系为：
-
第1层：1个节点
-
第2层：2个节点
-
第3层：4个节点
-
以此类推，第h层有 $2^{h-1}$ 个节点。
-
-
总查找次数
每层节点的查找次数等于该层节点数乘以层数，总查找次数为： $$ 1 \cdot 1 + 2 \cdot 2 + 3 \cdot 4 + \dots + h \cdot 2^{h-1} $$
通过数学推导，总查找次数可简化为： $$ (n+1)\log_2(n+1) - n - 1 $$
其中，$n = 2^h - 1$。
-
平均查找长度
将总查找次数除以节点数n，得到平均查找长度： $$ ASL = \frac{(n+1)\log_2(n+1) - n - 1}{n} = \log_2(n+1) - 1 $$
该公式表明，平均查找长度与树的高度（即$\log_2（n+1）$）呈线性关系。
三、示例计算
以有序表长度 12 为例：
-
$h = \log_2（13） \approx 3.7$
-
平均查找长度为： $$ \log_2(13) - 1 \approx 3.7 - 1 = 2.7 $$
实际计算结果为 $\frac{35}{12} \approx 2.92$，与理论值接近。
四、时间复杂度
二分查找的时间复杂度为 O（log n） ，平均查找长度进一步量化了其效率。例如，当n=1000时，ASL≈9.97，查找效率显著高于顺序查找（平均比较次数为n/2）。
总结
二分查找通过分治策略将查找范围减半，其平均查找长度为 $\log_2（n+1）-1$，适用于大规模数据的快速检索。