Question

1、对有序表(8,11,23,33,45,66,78,79,95)进行折半查找,画出查找23和77的过程，并画出其判定树

Answer 1

问：1、对有序表(8,11,23,33,45,66,78,79,95)进行折半查找,画出查找23和77的过程，并画出其判定树

答：折半查找23的过程如下：1. 选取有序表的中间元素45，比较23和45的大小，发现23小于45，所以查找范围缩小为前半部分(8,11,23,33)。2. 在缩小后的范围中，选取中间元素11，比较23和11的大小，发现23大于11，所以查找范围缩小为后半部分(23,33)。3. 在缩小后的范围中，选取中间元素23，发现23即为目标元素，查找成功。折半查找77的过程如下：1. 选取有序表的中间元素45，比较77和45的大小，发现77大于45，所以查找范围缩小为后半部分(66,78,79,95)。2. 在缩小后的范围中，选取中间元素78，比较77和78的大小，发现77小于78，所以查找范围缩小为前半部分(66)。3. 在缩小后的范围中，选取中间元素66，比较77和66的大小，发现77大于66，所以查找范围缩小为后半部分(78,79)。4. 在缩小后的范围中，选取中间元素79，比较77和79的大小，发现77小于79，所以查找范围缩小为前半部分(78)。5. 在缩小后的范围中，选取中间元素78，比较77和78的大小，发现77小于78，所以查找范围缩小为前半部分(无元素)。

答：6. 在缩小后的范围中，未找到目标元素，查找失败。判定树如下： 45(根节点) / \ 11 78 / \ / \8 23 66 95 / \ 79 77