有一个长度为12的有序表，按折半查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为

使用折半查找法查找长度为12的有序表时，每次查找可以将表的长度减半，因此最多需要进行log2(12) = 4次比较。在表内各元素等概率情况下，每个元素被查找到的概率为1/12，因此查找成功的概率为1/12。根据期望的线性性，平均比较次数等于每个元素被查找到的概率乘以查找该元素时需要的比较次数之和，即：

(1/12) * (1 + 2 + 3 + 4) = 5/6

因此，平均比较次数为5/6。

相关问题

顺折半查找法计算平均查找长度

### 二分查找的平均查找长度

对于二分查找而言，其平均查找长度可以通过理论推导得出。当在一个含有 \( n \) 个元素的有序列表中执行二分查找时，每次比较都将搜索区间减半直到找到目标值或确认不存在该值为止。

在理想情况下，即所有关键字等概率被查的情况下，二分查找的平均查找长度可由下述公式表达：

\[ ASL_{bin} = \frac{\sum\limits_{i=1}^{h}(D_i * P_i)}{n} \]

这里 \( h=\lceil\log_2{(n+1)}\rceil \)，\( D_i \) 表示第 i 层节点到根的距离加一（因为首次比较也算作一次探测），而 \( P_i \) 则代表位于层次 i 的记录数目占总记录数的比例[^1]。

简化后的形式通常写作：

\[ ASL_{bin} ≈ \log_2(n + 1) - 1 \]

此公式的含义在于，在最坏情况下的查找次数接近于以 2 为底 \( n+1 \) 的对数再减去 1，这是因为最后一次分割可能不会真正发生如果此时只剩下一个候选者[^2]。

因此，通过上述公式可以较为精确地估算出给定规模的数据集上应用二分查找算法所需的期望探测量。

import math

def calculate_average_search_length_binary(n):
    """Calculate the average search length of binary search."""
    return round(math.log2(n + 1) - 1, 4)

# Example usage with a list size of 10 elements.
print(calculate_average_search_length_binary(10))