数据结构 顺序查找的平均比较次数不是1+n⼀2吗？为什么是n⼀2？

平均次数是(n+1)/2，不是n/2。

被查找的数是第1个数，则需用第1个数和被查找的数比较，要比较1次。

被查找的数是第2个数，则需用第1个数、第2个数和被查找的数比较，要比较2次。

...

被查找的数是第n个数，则需用第1个数、第2个数、...、第n个数和被查找的数比较，要比较n次。

平均次数为(1+2+...+n)/n=(n+1)/2。

扩展资料：

顺序查找过程：从表中的最后一个记录开始，逐个进行记录的关键字与给定值进行比较，若某个记录的关键字与给定值相等，则查找成功，找到所查的记录；反之，若直到第一个记录，其关键字和给定值比较都不相等，则表明表中没有所查的记录，查找失败。

算法描述为

int Search(int d,int a[],int n)

{/*在数组a[]中查找等于D元素，若找到，则函数返回d在数组中的位置，否则为0。其中n为数组长度*/

int i ；

/*从后往前查找*/

for(i=n-1;a!=d;--i)

return i ;

/*如果找不到，则i为0*/

}

参考资料来源：百度百科-查找算法

你是对的，这个答案错了，
顺序表查找来说，最好的就是一次就可以找到，时间复杂度是O（1）
最坏是要比较n次,O(n)
如果查找不成功，要进行n+1次比较
由于关键字在任何一个位置的概率都是相同的，所以平均查找次数是n+1/2，时间复杂度还是O（n）

我对比了下书上的说法，觉得这样子想应该是OK的：
（1+n）/2是查找成功的情况下的平均查找次数

n/2是在任何情况下的平均查找次数（查找的可能失败可能成功）

Sales_data trans;
while(std::cin>>trans){
if(total.booKNO==trans.booKNO)
total+=trans;
else{
std::cout<

浙教版信息作业本算法与程序设计p52 (n+1)/2是对的