3.假设对有序表（5，10，24，31，42，55，63，72，87，99）进行二分查找，试回答下列问题： a)画出描述二分查找过程的判定树。 b)若查找元素72，需进行几次此较？ c）假定每个元素的查找概率相等，求查找成功时的平均查找长度

a) 描述二分查找过程的判定树如下：

                        42
                       /  \
                      /    \
                     /      \
                    24      72
                   /  \    /  \
                  /    \  /    \
                 10    31 55    87
                /  \   /      /  \
               /    \ /      /    \
              5    10 63    99    72

b) 查找元素 72，需要进行 2 次比较。

c) 假定每个元素的查找概率相等，查找成功的平均查找长度为：

$ASL = \frac{\sum_{i=1}^{n}dep(x_i)}{n} = \frac{1}{n}\sum_{i=1}^{n}depth_i$

其中，$ASL$ 表示平均查找长度，$dep(x_i)$ 表示元素 $x_i$ 的深度，$n$ 表示元素个数。在这个例子中，$n=10$，每个元素的查找概率相等，因此平均查找长度等于树中每个叶子结点深度的平均值。根据判定树可得，叶子结点的深度分别为 1，2，2，3，3，3，3，4，4，4，所以平均查找长度为：

(1+2+2+3+3+3+3+4+4+4)/10 = 3