做梦在马路上找不到出口,顺序查找不成功的平均查找长度是n还是n+1
- 作者: 壞钕
- 来源: 盐焗风水网
- 2022-05-17
顺序查找不成功的平均查找长度是n还是n+1
题目意思应该是无序的顺序表 平均查找长度为n+1（有序表并不是）
是因为在表中尾部（或头部）加入了一个辅助的符合查找条件的“哨兵”，然后从新表的另一头开始查找，此时新表长为n+1。 “哨兵”的关键字是符合查找条件的，故在新表中一定会查找成功，查找成功时返回它在表中的位置。原表长度为n，下标范围为0到n-1，如果查找到返回的值为n（头部时为0），即原表中查找失败。此时与新表中的所有元素都比较过，故为n+1。加入“哨兵”的好处是不需要再考虑判断数组越界的问题，如果不加入“哨兵”，还需考虑数组下标越界问题，比较次数更多。
推荐阅读
