Question

72. 对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找

72. 对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的 为什么啊、、

Answer 1

对于查找成功，无论有序表或无序表，一个一个地分别顺序查找，查找到所有n个数据的总长度 都是： 1+2+。。。+n, 所以平均查找长度都是 (n+1)/2, 是相同的
对于查找失败，设有序表的序是从小到大，如果 所查找的b 有 a(i-1)<b<ai, 则在i处即可停止查找。所以平均查找长度<n.
而无序表无论b的大小，都必须查遍整个表才能得出查找不到的结论，所以查找长度总是n.