【经验分享】数据结构——折半查找的概念,折半查找的平均查找长度、查找成功、查找不成功,例题:100个元素折半查找,查找成功的最多比较次数

2024-08-17 08:33:45 浏览数 (1)

折半查找的概念与性能分析

折半查找(Binary Search)是一种高效的查找算法,适用于在已排序的数组中快速定位特定元素。它通过将搜索区间对半分,逐步缩小查找范围,从而实现高效查找。其时间复杂度为

O(log_2 N)

,使其在处理大规模数据时表现优异。

折半查找的基本概念

折半查找的工作原理如下:

  1. 初始化:设定两个指针 lowhigh,分别指向数组的起始和结束位置。
  2. 计算中点:计算当前区间的中点 mid,即
(low high) / 2

  1. 比较
    • 如果目标元素等于中点元素,则查找成功。
    • 如果目标元素小于中点元素,则在左半部分继续查找,将 high 设置为 mid - 1
    • 如果目标元素大于中点元素,则在右半部分继续查找,将 low 设置为 mid 1
  2. 重复:继续执行上述步骤,直到找到目标元素或区间 low 超过 high(表示查找失败)。
平均查找长度(ASL)的计算

折半查找的 平均查找长度(ASL) 衡量了查找操作的效率。在折半查找中,ASL 的计算公式如下:

  1. 查找成功的 ASL 查找成功的平均查找长度(ASL)计算公式为:
text{ASL}_{text{成功}} = frac{1}{n} sum_{i=1}^{n} l_i

其中

l_i

是第

i

个元素的查找深度,

n

是元素总数。这个公式计算了每个成功查找的平均比较次数。

  1. 查找不成功的 ASL 查找不成功的平均查找长度(ASL)计算公式为:
text{ASL}_{text{不成功}} = frac{1}{n 1} sum_{j=1}^{n 1} (l_j - 1)

其中

l_j

是第

j

个节点的深度,

n 1

是节点总数,包括额外的虚拟节点(表示查找不成功的情况)。这个公式计算了在查找失败时,所需的平均比较次数。

进一步地,对于大规模数据,查找不成功的 ASL 近似为

log_2 n

,因为树的深度与数据的对数成正比。


示例:100个元素的折半查找

假设我们在一个包含 100 个元素的已排序数组中进行折半查找:

  1. 查找成功的 ASL 计算成功查找的 ASL 需要对每个元素进行深度计算,然后求其平均值。由于公式涉及到每个元素的具体深度,具体计算可能较复杂,但可以使用以下公式的简化形式进行近似:
text{ASL}_{text{成功}} = frac{(n 1) log_2 (n 1)}{n} - 1

对于

n = 100

text{ASL}_{text{成功}} = frac{101 times log_2 101}{100} - 1 approx frac{101 times 6.664}{100} - 1 approx 6.741 - 1 = 5.741

平均比较次数大约为 5.741 次

  1. 查找不成功的 ASL 对于不成功的查找,ASL 为:
text{ASL}_{text{不成功}} = log_2 100 1 approx 6.644 1 = 7.644

平均比较次数大约为 7.644 次

总结一

折半查找是一种高效的查找算法,适用于已排序的数组。其平均查找长度(ASL)可以通过公式

frac{(n 1) log_2 (n 1)}{n} - 1

计算。在包含 100 个元素的数组中,折半查找的成功查找的平均比较次数约为 5.741 次,而不成功查找的平均比较次数约为 7.644 次。这些性能指标有助于评估折半查找在实际应用中的效率,并为优化查找操作提供依据。


示例:100个元素折半查找,查找成功的最多比较次数

对于折半查找(Binary Search),成功查找时的最多比较次数是与查找树的高度相关的。在最坏的情况下,即查找成功但需要经过树的所有层时,这个次数等于树的最大深度。

折半查找的树结构

在折半查找中,数据被组织成一棵平衡的二叉搜索树。树的高度与元素数量

n

之间的关系可以用对数函数来描述:

text{高度} = lceil log_2 (n 1) rceil

其中:

log_2 (n 1)

是以 2 为底的对数,表示树的高度。

lceil cdot rceil

表示向上取整。

示例:100个元素折半查找

对于一个包含 100 个元素的已排序数组:

  1. 计算树的高度 计算树的最大深度(即最多比较次数):
text{最大深度} = lceil log_2 (100 1) rceil

计算 (log_2 101):

log_2 101 approx 6.664

向上取整:

lceil 6.664 rceil = 7

因此,最多需要 7 次比较 来成功查找一个元素。

总结二

对于一个包含 100 个元素的折半查找,成功查找的最多比较次数为 7 次。这是因为在最坏的情况下,查找成功需要遍历整个树的深度,而树的深度为 (lceil log_2 (100 1) rceil)。这种效率使得折半查找在处理大量数据时非常高效。

0 人点赞