如何计算折半查找的平均查找长度?

Answer 1

折半查找可以借助于一个二叉树来描述。

为了简化讨论，则把这棵树近似看成满二叉树，设二叉树的高度为h(h>1)

则，根据二叉树的性质，它有最大节点数n=2^h-1，

则h=log2(n+1) (2是底数)。那么二叉树的第j层节点数为：2^(j-1)

假定每个元素的查找概率相等，则，pi=1/n (pi为第i个节点的查找概率)

那么平均查找长度为 1/n*（1*2^0+2*2^1+3*2^2+……+j*2^(j-1)）

则经过化简计算，得平均查找长度为：(（n+1）/n ) *log2(n+1)-1 (其中对数中的2为底数：即log以2为底（n+1)的对数）

注 : 当n很大时 ，可近似为 log2(n+1)-1

搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找。

而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

扩展资料：

假设有已经按照从小到大的顺序排列好的五个整数a0~a4，要查找的数是X，其基本思想是： 设查找数据的范围下限为l=0，上限为h=4，求中点m=（l+h）/2，用X与中点元素am比较，若X等于am，即找到，停止查找。

否则，若X大于am，替换下限l=m+1，到下半段继续查找；若X小于am，换上限h=m-1，到上半段继续查找；如此重复前面的过程直到找到或者l>h为止。如果l>h，说明没有此数，打印找不到信息，程序结束。

用待查关键字值与中间位置的关键字值进行比较；若相等，则查找成功若大于，则在后（右）半个区域继续进行折半查找若小于，则在前（左）半个区域继续进行折半查找。

对确定的缩小区域再按折半公式，重复上述步骤。最后，得到结果：要么查找成功， 要么查找失败。折半查找的存储结构采用一维数组存放。

参考资料来源：百度百科——折半查找法

Answer 2

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

Answer 3

如果你是要求给定的一组有序的记录关键字序列的话，例如{13,18,24,35,47,50,62,83,90}.你要先求出其折半查找判定树。{47（18（13,24（ ，35）），62（50,83（ ，90）））}.这树你可以还原吧。所以平均查找长度为（ 1*1+2*2+3*4+4*2）/9=25/9，只看每一层的结点数。至于那个公式的话，书上有，你就自己看吧。

Answer 4

你是说纸上计算呢还是编程计算呢？如果是纸上计算，把N个数化为一个N个叶子的二叉树，平均查找长度就是从根到每个叶子的长度的平均值

如果你说编程，那简单的方法是N个数中，每个数的查找长度，然后加一起除以N就好了呗

Answer 5