有序表对半搜索算法分析：二叉判定树、成功与失败平均查找长度

(1) 二叉判定树如下图所示：

           5
          / \ 
         /   \ 
        /     \ 
       2       8
      / \     / \ 
     /   \   /   \ 
    0     3 6     9
         /     / \ 
        /     /   \ 
       1     7    10

其中，根节点为第5个元素30，左子树代表小于30的元素，右子树代表大于等于30的元素。左子树的根节点为第2个元素17，左子树代表小于17的元素，右子树代表大于等于17的元素。右子树的根节点为第8个元素60，左子树代表小于60的元素，右子树代表大于等于60的元素。依此类推。

(2) 搜索成功时，平均查找长度等于每个元素被查找的概率乘以查找该元素时的比较次数之和。由于该有序表中每个元素被查找的概率相等，因此平均查找长度为：

$ASL = \frac{1}{11}(1\times1 + 1\times2 + 1\times2 + 1\times3 + 1\times3 + 1\times3 + 1\times4 + 1\times4 + 1\times4 + 1\times4 + 1\times4) = \frac{25}{11} \approx 2.27$

(3) 搜索失败时，平均查找长度等于查找失败时访问的比较次数。对于二叉判定树，查找失败时访问的比较次数等于从根节点到叶子节点的路径长度。该有序表的二叉判定树为平衡的，因此叶子节点的深度均为4。因此，平均查找长度为：

$ASL = 4 = \log_2(11) \approx 3.46$