此间大牛多，请教算法高手一个问题

数值分析

: g! l+ z* V( U
+ w7 n9 }3 f# }8 o* b8 L  z+ ?您对答案的理解似乎有误。
随机变量X是测试过的元素的数目
而随机变量Xi是另一组随机变量，每一个都是个indicator，取值是0或者1，含义为第i个元素是否被测试过，而不是该元素是否等于欲查找的值。
所以才有E(x)=sum(E(Xi))。
而如果 A[ i ]!= x，那么k个x值元素将整个数组分为了k+1个区间，而我们检查了这个元素，所以这个元素必须位于第一个区间，所以概率是1/(k+1)
您再想想？

数值分析

3 p8 Y% C3 C4 r

老福 发表于 2022-3-26 12:01
其实原文的解释似是而非，试想i=1的情形，对于概率P(X1=1), 无论A1是不是x, 这个概率应该是1, 而不是1/（ ...

3 f+ R! w9 [2 E5 j% i. i
我觉得这个答案的作者其实是吧下标i作为元素的编号，而不是位置。
1 P2 E3 ^+ m+ u, r9 t0 d* ]否则没法按元素是否等于x来分类，因为某一个位置是否等于x本身就是个随机事件。

而这个答案的作者其实是把每一个元素编了号，然后再考虑这个元素在数组中的位置的。故此对应于某一个元素，其是否等于x是个确定的事件，所以元素可以分为两类讨论，等于x的和不等于x的。
$ o% h4 c2 }4 H, ^4 x所以A[ i ]这个写法有点误导，这里这个A并不是要做搜索的那个数组，而是所有元素的列表。