在长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的_

腐草为萤

不是很懂为什么是（n+1）/2,而不是n/2,谁能给我解答下

发表于 2017-03-07 22:35:42 回复(6)

SXISZERO

长度为n的线性表顺序查找x，则查找次数可能是1,2,3,...,n次，则和sum为n*(1+n)/2，所以平均查找次数为sum/n=(n+1)/2

发表于 2017-03-11 22:34:50 回复(1)

如此201809271455765

如题：在长度为n的顺序线性表中顺序查找值为x的元素时

理解：x是顺序线性表中的元素

所以，运气好第一次就找到，运气不好找到最后才找到

因此，查找次数可能是1 、2 、3 ...n次。等差数列前n项和（自己百度），累加得sum=n*(n+1)/2

这是对n个元素查找累加的的结果，因此平均一下，sum/n 便是答案。

发表于 2018-09-27 17:12:15 回复(0)

牛客小妞号

长度为n的线性表顺序查找x，则查找次数可能是1,2,3,...,n次，则和sum为n*(1+n)/2，所以平均查找次数为sum/n=(n+1)/2

发表于 2021-06-24 23:43:57 回复(0)

宋化志

查找第一个数的次数为1，第二个数的次数为2，……以此类推，第n个数为n，总共需要的查找次数为1+2+……+n=n(n+1)/2,平均查找次数为n(n+1)/2/n=(n+1)/2

发表于 2017-06-26 17:40:59 回复(0)

NightCrow2023

缘来如此，

发表于 2021-12-18 11:00:20 回复(0)

就是牛p

用等差数列的求和公式能算出来

发表于 2020-12-13 12:26:31 回复(0)

不拉不拉

sum = n*(1+n) / 2

averageO = sum / n = （n+1）/ n

发表于 2020-06-24 16:43:40 回复(0)

大哥给个offer再走啊

应该是最后还要再对比一次所以分子是＋1

发表于 2019-03-04 20:20:03 回复(0)

yan_lj

平均查找长度和平均比较次数是一个意思

发表于 2019-02-19 19:37:19 回复(0)

进阶的土豆

顺序表顺序查找，每个元素查找成功次数可能为1~n次，n个元素为n*（1+n）/2 次，每个元素平均为（1+n）/2 次

发表于 2019-02-19 10:03:58 回复(0)

RenaissanceWhy

比如n=2顺序线性表，查询次数1次或2次，平均就是(1+2)/2=1.5次。

发表于 2017-03-10 01:01:53 回复(0)

强者为尊

类似于1到n的均匀分布,均匀分布的期望在区间中间,所以查找成功时的平均查找长度是(n+1)/2

发表于 2016-12-08 10:24:24 回复(0)

在长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的