有序序列:{1,2,3,4,5,6,7,8,10,11,12,13},现对该序列进行折半查找 (1) 画出该序列在折半查找下的比较树/判定树
时间: 2023-10-04 15:04:23 浏览: 25
以下是该序列在折半查找下的比较树/判定树:
```
7
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
4 11
/ \ / \
/ \ / \
/ \ / \
/ \ / \
2 5 10 12
/ \ / \ / \ / \
/ \ / \ / \ / \
1 3 - - - - 13 -
```
在折半查找过程中,每次都会将当前区间分成两个子区间。比较树/判定树上的每一个节点表示一个子区间,节点上的数字表示该区间的中间位置。
例如,根节点7表示整个序列的区间[1,13],其左子树表示区间[1,4],右子树表示区间[10,13]。左子树的根节点4表示区间[1,7]的中间位置,其左子树表示区间[1,2],右子树表示区间[5,7],以此类推。
当我们要查找一个元素时,从根节点开始,如果该元素小于当前区间的中间元素,则进入左子树,否则进入右子树,直到找到目标元素或者无法继续划分区间。