⑨ 假设顺序表按关键宇自大至小有序．试改写教科书 . 1. 节中的顺序查找 算法，将监视哨设在高 标端。然后画出描述此查找过程的判定树．分别求出等概率情况 下查找成功和不成功时的平均查找长度

将监视哨设在高标端的顺序查找算法如下所示：

int seq_search(int arr[], int n, int target) {
    arr[n] = target; // 设置监视哨

    int i;
    for (i = 0; arr[i] > target; i++) {
        ; // 顺序查找
    }

    if (i == n) {
        return -1; // 没有找到目标元素
    } else {
        return i; // 返回目标元素的下标
    }
}

查找成功时的判定树如下所示：

                 +-------------------+
                 | arr[i] == target  |
                 +-------------------+
                           |
                           v
                +---------------------+
                | return i;           |
                +---------------------+

查找不成功时的判定树如下所示：

                 +-------------------+
                 | arr[i] > target   |
                 +-------------------+
                           |
                           v
                  +------------+
                  | i == n     |
                  +------------+
                           |
                           v
                +---------------------+
                | return -1;          |
                +---------------------+

因为是等概率情况下的查找，所以成功和不成功的概率相等，平均查找长度为：

ASL = (1/n) * (1 + 2 + ... + n/2 + (n+1)/2)
    = (1/n) * [(n/2) * (n/2 + 1) / 2 + (n+1) / 2]
    = (n+3) / 4

因此，无论查找是否成功，平均查找长度都为 `(n+3)/4`。