有序序列:{1,2,3,4,5,6,7,8,10,11,12,13},现对该序列进行折半查找 请画出该序列在折半查找下的比较树/判定树
时间: 2023-10-04 11:03:35 浏览: 40
以下是该序列在折半查找下的比较树/判定树:
```
7
/ \
/ \
/ \
4 11
/ \ / \
/ \ / \
2 5 10 12
/ \ / \ / \ / \
1 3 / \ / \ / \
6 8 9 - - 13
/ \
- -
```
其中,每个节点表示一个比较操作,左子树为比当前元素小的部分,右子树为比当前元素大的部分。比较树/判定树的深度为$log_2n$,其中$n$为序列的元素数量。
相关问题
有序序列:{1,2,3,4,5,6,7,8,10,11,12,13},现对该序列进行折半查找 (1) 画出该序列在折半查找下的比较树/判定树
以下是该序列在折半查找下的比较树/判定树:
```
7
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
4 11
/ \ / \
/ \ / \
/ \ / \
/ \ / \
2 5 10 12
/ \ / \ / \ / \
/ \ / \ / \ / \
1 3 - - - - 13 -
```
在折半查找过程中,每次都会将当前区间分成两个子区间。比较树/判定树上的每一个节点表示一个子区间,节点上的数字表示该区间的中间位置。
例如,根节点7表示整个序列的区间[1,13],其左子树表示区间[1,4],右子树表示区间[10,13]。左子树的根节点4表示区间[1,7]的中间位置,其左子树表示区间[1,2],右子树表示区间[5,7],以此类推。
当我们要查找一个元素时,从根节点开始,如果该元素小于当前区间的中间元素,则进入左子树,否则进入右子树,直到找到目标元素或者无法继续划分区间。
若有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)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://img-home.csdnimg.cn/images/20210720083646.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)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)