对于有序表:6,7,9,13,17,18,20,31,45,67,87，如果进行折半查找，请回答下列问题： （1）描述折半查找算法，画出折半查找过程的判定树。 （2）若查找元素67，需要依次与哪些元素比较？ （3）假定每个元素的查找概率相等，求查找成功时的平均查找长度。

（1）折半查找（Binary Search），也称为二分查找，是一种在有序数组中寻找特定元素的搜索算法。它的基本步骤如下：

- 首先，确定待搜索区间的首尾索引，通常是初始的0和数组长度减一。
- 计算中间索引，即 (左索引 + 右索引) / 2。
- 比较中间元素值与目标值：
- 如果中间元素正好等于目标值，查找结束。
- 如果中间元素大于目标值，说明目标应在前半部分区间内，更新右索引为中间索引减一。
- 如果中间元素小于目标值，说明目标应在后半部分区间内，更新左索引为中间索引加一。
- 重复以上步骤直到找到目标或区间为空。

对于这个问题，判定树会是一个递归结构，从根节点开始，每次分支都是基于比较操作的结果。例如，查找67的过程会是这样的：

       67
      / \
     45  87
    /     \
   31     67
  /         \
 18         67

- 左边分支会跳过18，然后继续比较31...
- 直到最后一个节点就是我们需要比较的。

（2）查找元素67的过程如下：
- 与87比较，67 < 87，所以缩小范围到左半部（45、31）；
- 与45比较，67 > 45，再与31比较；
- 与31比较，67 > 31，再与18比较；
- 与18比较，67 > 18，由于左半部已无合适元素，转向右半部并与67比较（发现匹配）。

（3）平均查找长度（ASL，Average Search Length）计算公式是所有可能情况下的查找次数除以总的元素数。因为每次比较都将查找范围减半，所以最终只会查找一次。假设查找成功的概率为1/11（因为有11个元素），则平均查找长度为：
ASL = (1 * 1 + (11-1) * (1/2)) / 11 = (1 + 5) / 11 ≈ 6 / 11