线性搜索比较次数计算方法咨询（CLRS自学疑问）

嘿，我正好对CLRS里线性搜索的比较次数分析这块很熟悉，咱们结合书中的伪代码一步步拆解你的疑问，帮你理清思路。

首先先把你提到的带while循环的线性搜索伪代码放出来（这应该是你正在看的版本）：

LINEAR-SEARCH(A, v)
1  i = 1
2  while i <= length[A] and A[i] != v
3      i = i + 1
4  if i <= length[A]
5      return i
6  else
7      return NIL

接下来逐个解答你的问题：

核心疑问拆解 #

1. i <= length[A] 的比较次数 #

这个条件的比较次数分两种场景：

• 当目标元素v在数组中时：假设v在第k个位置（1≤k≤n，n=length[A]）。循环会执行k次条件检查（每次循环都先判断i<=n），加上循环结束后第4行的1次i<=n判断，总共是 k+1 次。
• 当v不在数组中时：循环会执行n次i<=n的判断（每次都为真），加上循环结束后第4行的1次i<=n判断（为假），总共是 n+1 次。

2. A[i] != v 是否需要计入比较次数 #

当然需要！这是线性搜索里的核心判断条件，而且要结合短路求值逻辑来看：

• 只有当i<=n为真时，才会执行A[i]!=v的比较（逻辑与的短路特性）。
• 找到v的场景：前k-1次循环中，A[i]!=v都为真（共k-1次比较）；第k次循环中，A[i]!=v为假（1次比较），所以总共是 k 次。
• 没找到v的场景：n次循环里A[i]!=v全为真，所以是 n 次。

3. i > length[A] 是否算作1次比较 #

其实你说的i>length[A]，对应伪代码里第4行的i<=length[A]判断为假的情况——这确实是1次比较，只会在v不在数组中的场景下发生，也就是循环结束后用来确认“遍历完整个数组都没找到v”的那次判断。

分场景总比较次数汇总 #

最好情况（v在数组第1个位置） #

• 循环条件检查1次（i<=n真 + A[i]!=v假），加上第4行的i<=n判断1次，总比较次数是 2+1=3 次。

最坏情况（v不在数组中） #

• 循环内每次检查2次比较（i<=n真 + A[i]!=v真），共2*n次；加上第4行的1次判断，总次数是 2n+1 次。

平均情况（假设v在数组中的概率为p，每个位置概率相等） #

• 找到v的平均比较次数：(sum_{k=1到n} (2k+1))/n = (2*(n(n+1)/2) +n)/n = n+2
• 没找到的比较次数：2n+1
• 整体平均次数：p*(n+2) + (1-p)*(2n+1)

最后要说明的是，不同教材的分析可能会有细微差异，但CLRS里的标准分析就是基于上述的短路求值和分步判断逻辑来统计比较次数的，核心是把每一次实际执行的条件判断都算进去。

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