对有序表(3,5,8,10,12,15,18,20,30,35,40,42,44,50)进行折半查找,在表内各元素等概率情况下查找成功时的平均查找长度为( )。 A. 37/14 B. 45/14 C. 41/14 D. 3
时间: 2023-09-19 09:07:11 浏览: 53
折半查找的基本思想是:每次将待查找区间的中间位置与目标值进行比较,如果相等则查找成功;否则根据比较结果,将待查找区间缩小一半,继续进行查找,直到找到目标值或者待查找区间为空。
在这个问题中,有序表中一共有 $n=14$ 个元素。对于任意一个元素,折半查找的最坏情况下需要进行 $\lfloor \log_2 n \rfloor+1=4$ 次比较,即将区间缩小到只有一个元素。但是,这里假设每个元素被查找的概率是等概率的,因此查找成功时的平均查找长度等于所有元素被查找的概率乘以它们的查找长度之和。对于有序表中的每个元素,它的查找长度可以用下面的公式来计算:
$$L_i=1+\lfloor \log_2 (n+1-i) \rfloor$$
其中 $i$ 表示元素在有序表中的位置,$1$ 表示第一次比较,$\lfloor \log_2 (n+1-i) \rfloor$ 表示缩小区间的次数。
根据上述公式,可以计算出每个元素的查找长度,并计算出每个元素被查找的概率。这里只列出每个元素的查找长度:
| 元素 | 查找长度 |
| ---- | -------- |
| 3 | 2 |
| 5 | 2 |
| 8 | 3 |
| 10 | 3 |
| 12 | 3 |
| 15 | 4 |
| 18 | 4 |
| 20 | 4 |
| 30 | 5 |
| 35 | 5 |
| 40 | 5 |
| 42 | 5 |
| 44 | 5 |
| 50 | 5 |
因此,查找成功时的平均查找长度为:
$$\frac{1}{14}(2+2+3+3+3+4+4+4+5+5+5+5+5+5)=\frac{45}{14}$$
因此,答案是 B. 45/14。
相关推荐
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)