当前位置：新励学网 > 秒知问答 > 平均寻道长度公式

平均寻道长度公式

发表时间：2024-07-28 03:10:35 来源：网友投稿

折半查找可以借助于一个二叉树来描述。为了简化讨论，则把这棵树近似看成满二叉树，设二叉树的高度为h(h>1) 则，根据二叉树的性质，它有最大节点数n=2^h-1，则h=log2(n+1) (2是底数)。那么二叉树的第j层节点数为：2^(j-1) 假定每个元素的查找概率相等，则，pi=1 (pi为第i个节点的查找概率) 那么平均查找长度为 1*（1*2^0+2*2^1+3*2^2+……+j*2^(j-1)）则经过化简计算，得平均查找长度为：(（n+1） ) *log2(n+1)-1 (其中对数中的2为底数：即log以2为底（n+1)的对数）

注 : 当n很大时，可近似为 log2(n+1)-1 搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找。

而且跟开始一样从中间元素开始比较。

如果在某一步骤数组为空，则代表找不到。

这种搜索算法每一次比较都使搜索范围缩小一半。

免责声明：本站发布的教育资讯（图片、视频和文字）以本站原创、转载和分享为主，文章观点不代表本网站立场。

如果本文侵犯了您的权益，请联系底部站长邮箱进行举报反馈，一经查实，我们将在第一时间处理，感谢您对本站的关注！