折半查找平均查找长度：15 个关键字的示例

在 15 个关键字的有序表中，每个关键字的查找次数相同，折半查找的查找成功的平均查找长度为 log2(15)+1 = 4.91。

折半查找原理

折半查找是一种高效的查找算法，适用于有序表。它通过不断将查找范围缩小一半来查找目标关键字。

平均查找长度计算

平均查找长度是指查找成功时，平均需要比较的关键字次数。对于折半查找，平均查找长度可以用以下公式计算：

log2(n) + 1

其中，n 是关键字的数量。

示例：15 个关键字

对于 15 个关键字的有序表，平均查找长度为：

log2(15) + 1 = 4.91

结论

折半查找的平均查找长度与关键字数量的对数成正比。这表明，随着关键字数量的增加，折半查找的效率会逐渐降低，但仍然比线性查找效率高很多。