盖特|盖特CS 1996 |问题38

在长度列表中，在成功的顺序搜索中进行的键比较的平均数 （A） 日志n （B） （n-1）/2 （C） n/2 （D） （n+1）/2 答复: （D） 说明： 如果元素位于1个位置，则需要进行1次比较。 如果元素位于2个位置，则需要2个比较。 如果元素位于3个位置，则需要进行3次比较。 类似地，如果元素位于n位置，则需要n个比较。

Total comparison 
= n(n+1)/2

For average comparison 
= (n(n+1)/2) / n 
= (n+1)/2 

选项（D）是正确的。 这个问题的小测验