有序序列:{1,2,3,4,5,6,7,8,10,11,12,13},现对该序列进行折半查找 (1) 画出该序列在折半查找下的比较树/判定树
时间: 2023-10-04 13:03:35 浏览: 4
以下是该序列的折半查找比较树/判定树:
```
7
/ \
4 10
/ \ / \
2 5 8 12
/ \ / \ / \ / \
1 3 - - - - 11 13
```
根据比较树/判定树,我们可以看到在最坏情况下,折半查找算法需要进行4次比较才能找到元素13。
相关问题
有序序列:{1,2,3,4,5,6,7,8,10,11,12,13},现对该序列进行折半查找 请画出该序列在折半查找下的比较树/判定树
以下是该序列在折半查找下的比较树/判定树:
```
7
/ \
/ \
/ \
4 11
/ \ / \
/ \ / \
2 5 10 12
/ \ / \ / \ / \
1 3 / \ / \ / \
6 8 9 - - 13
/ \
- -
```
其中,每个节点表示一个比较操作,左子树为比当前元素小的部分,右子树为比当前元素大的部分。比较树/判定树的深度为$log_2n$,其中$n$为序列的元素数量。
若有18个元素的有序表存放在一维数组A[19]中,第一个元素放A[1]中,现进行二分查找,则查找A[3]的比较序列的下标依次为()。 A 9,7,2,3 B 9,4,2,3 C 1,2,3 D 9,2,3
首先需要明确二分查找的过程:每次取中间位置的元素与目标元素进行比较,根据比较结果判断目标元素在左半部分还是右半部分,然后在相应的半部分继续执行二分查找,直到找到目标元素或者确定目标元素不存在。
因为有序表存储在一维数组A[19]中,所以可以按照下标进行访问,即A[1]表示第一个元素,A[2]表示第二个元素,以此类推。
根据二分查找的过程,查找A[3]的比较序列的下标依次为:
1. 取中间位置的元素比较,即比较A[10]和A[3],发现A[10]>A[3],目标元素在左半部分。
2. 在左半部分中取中间位置的元素比较,即比较A[5]和A[3],发现A[5]>A[3],目标元素在左半部分。
3. 在左半部分中取中间位置的元素比较,即比较A[3]和A[3],发现A[3]=A[3],目标元素就是A[3],查找成功。
因此,查找A[3]的比较序列的下标依次为:D 9,2,3。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)