渣新刚注册csdn求教各位大神一个简单的二分法问题！谢谢！非伸手党..

Question

一个排列好的从小到大的数组，其长度是n。 假设x在这个数组里面的概率是n/m 。那么使用二分法在这个数组里查找x。 平均要查找多少次？我的想法：如果不在数组里面，概率是(m-n)/m ,共执行 （log2n +1） 次 ， 所以期望为  （log2n +1）* (m-n)/m 如果在数组里面，概率是n/m ，有可能执行1,2,3,4....（log2n +1）次..所以期望为n/m*（1*1/n+2*2/n+3*4/n+...+(log2n +1)*2^(log2n)/n)把它们相加，有错吗？为什么我算出来和答案相差很多啊...

Answer 1

平均值得公式不是n*(1+n)/2吗？存在于数组中的概率=n/m*(log2n x (1+log2n)/2)

Answer 2

n*(1+n)/2 是怎么来的啊？
1,2,3,4...,log2n不就是等差数列吗，等差数列求和不就是n*(1+n)/2吗

Answer 3

n*(1+n)/2 是怎么来的啊？
1,2,3,4...,log2n不就是等差数列吗，等差数列求和不就是n*(1+n)/2吗虽然一个数在数组里面的几率是n/m.但是那个数要用多少次找到的概率还是不同啊，
比如只用一次就找到那个数的概率为1/n，用两次找到的概率为2/n ,用三次找到的概率为4/n.....