对于一个长度为N的顺序表,查找不成功时的平均查找长度是?请问是N+1吗?（希望缎给出详细的解释……）

Question

对于一个长度为N的顺序表,查找不成功时的平均查找长度是?请问是N+1吗?（希望缎给出详细的解释……）

Answer 1

不是.好多说是n+1只是说最大可能查找长度,没有考虑到ASL公式里头概率.
假设以等概率查找不到,则判断找不到需要n+1次查找（前n次每个节点比较过,最后一次判断找不到）,概率为1/(n+1).
不失一般性,假定链表无头节点,从第一节点开始查找（从尾节点开始查找也一样）.（有头节点则从第二节点开始,不影响结果）.
由于计算平均查找长度是以最坏可能性考虑,故从第一个节点开始比较到尾节点,需要比较n次,查找长度n；从第二个节点开始比较到尾节点,需要比较n-1次,查找长度n-1；.,最后一个节点比较1次,查找长度1.
总长数＝n+(n-1)+...+2+1=n(n+1)/2
查找不成功时平均查找长度＝(n(n+1)/2)* (1/(n+1))=n/2
具体算的过程类似查找成功时平均查找长度（ASL=(n+1)/2).从宏观来讲,两种平均查找长度时间复杂度一样,微观来讲,找不到的比找到的平均查找长度小,找不到的可能性更大.这也是二分法优化的时候先判断找不到最后才判断找到的,但实际上好多教材二分法都是先判断找到才判断找不到.