1、已知对有序序列{6， 11， 17， 29， 33， 34， 37， 45， 77， 80}进行折半查找，要求： （1） 请画出对应的判定树；（2） 请问成功查找 17 和 77 需要分别与哪些关键字进行比较；（3） 在等概率的假设下， 请计算出查找成功时的平均查找长度和查找失败时的平均查找长度。

抱歉，我之前的回答有误。下面是正确的回答：

1. 对应的判定树如下所示：

        34
     /      \
   11        77
  /  \      /  \
6   17   45   80
      \
      29
       \
       33
        \
        37

2. 成功查找 17 需要与 34 进行比较，成功查找 77 需要与 77 进行比较。

3. 在等概率的假设下，查找成功时的平均查找长度为 (1+2)/2 = 1.5，查找失败时的平均查找长度为 (1+2+3+4+4+5+5+5+5+5)/10 = 4.1。其中，成功查找需要比较的次数为判定树的深度，也就是 log2(10) = 3.32，但是由于节点只能是整数，所以向上取整为 4。失败查找需要比较的次数为该节点所在的层数。

相关问题

已知一有序的序列{1,3,5,7,9}，采用顺序查找和折半法分别查找3和6。

顺序查找：从序列的第一个元素开始，依次比较每个元素，直到找到目标元素或者遍历完整个序列。对于查找3，需要比较1、3，找到了目标元素3；对于查找6，需要比较1、3、5、7、9，遍历完整个序列后未找到目标元素6。

折半法：首先确定序列的中间位置，将目标元素与中间位置的元素进行比较，如果相等则找到目标元素，如果目标元素比中间位置的元素小，则在左半部分继续查找，否则在右半部分继续查找，直到找到目标元素或者左右两部分都没有目标元素。对于查找3，首先将序列分为{1,3,5}和{7,9}两部分，中间位置为3，目标元素与中间位置的元素相等，找到目标元素3；对于查找6，首先将序列分为{1,3,5}和{7,9}两部分，中间位置为5，目标元素比中间位置的元素小，在左半部分{1,3,5}中继续查找，中间位置为3，目标元素比中间位置的元素大，在右半部分{5}中继续查找，未找到目标元素6。

已知序列8,15,32,34,46,57,63,71,84,92,109，则用折半查找法查找15需要进行( )次比较.

折半查找法，也称二分查找法，是一种常用的查找算法，其时间复杂度为 O(log n)。

在给定的有序序列中查找一个元素，折半查找法的具体操作如下：

1. 将序列的中间元素与要查找的元素进行比较。
2. 如果中间元素等于要查找的元素，则查找成功，返回中间元素的下标。
3. 如果中间元素大于要查找的元素，则在序列左半部分继续进行折半查找。
4. 如果中间元素小于要查找的元素，则在序列右半部分继续进行折半查找。
5. 如果左右两个部分都没有查找到要找的元素，则查找失败。

对于给定的序列8,15,32,34,46,57,63,71,84,92,109，查找元素 15，具体操作如下：

1. 将序列的中间元素 46 与要查找的元素 15 进行比较，发现 15 < 46。
2. 在序列的左半部分 (8, 15, 32, 34) 中继续进行折半查找。
3. 将左半部分的中间元素 15 与要查找的元素 15 进行比较，发现相等，查找成功，返回中间元素的下标 1。

因此，查找元素 15 需要进行 2 次比较。