1.编写一个程序，输出在顺序表（1，2，3，4，5，6，7，8，9，10）中采用折半查找方法查找关键字9的过程。 2.编写一个程序，对于给定的关键字序列，构造一棵二叉排序树bt，并求bt在查找成功和失败情况下的平均查找长度。

1.以下是在顺序表中采用折半查找方法查找关键字9的过程：
1. 初始化左指针left = 0，右指针right = 9；
2. 计算中间位置mid = (left + right) / 2 = 4；
3. 将中间位置元素与关键字9进行比较，发现中间位置元素为5，比9小，因此在右半部分继续查找；
4. 更新左指针为mid + 1 = 5，右指针不变，即left = 5，right = 9；
5. 计算中间位置mid = (left + right) / 2 = 7；
6. 将中间位置元素与关键字9进行比较，发现中间位置元素为8，比9小，因此在右半部分继续查找；
7. 更新左指针为mid + 1 = 8，右指针不变，即left = 8，right = 9；
8. 计算中间位置mid = (left + right) / 2 = 8；
9. 将中间位置元素与关键字9进行比较，发现中间位置元素为9，与关键字相等，查找成功。

2.以下是给定关键字序列构造二叉排序树并计算平均查找长度的程序：

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def insert(root, val):
    if not root:
        return TreeNode(val)
    if val < root.val:
        root.left = insert(root.left, val)
    elif val > root.val:
        root.right = insert(root.right, val)
    return root

def search(root, val):
    if not root or root.val == val:
        return root
    if val < root.val:
        return search(root.left, val)
    else:
        return search(root.right, val)

def get_depth(root, val, depth):
    if not root:
        return 0
    if root.val == val:
        return depth
    if val < root.val:
        return get_depth(root.left, val, depth + 1)
    else:
        return get_depth(root.right, val, depth + 1)

def get_avg_depth(root, vals):
    n = len(vals)
    total_depth = 0
    for val in vals:
        depth = get_depth(root, val, 1)
        total_depth += depth
    return total_depth / n

# 构造二叉排序树
nums = [4, 2, 6, 1, 3, 5, 7]
root = None
for num in nums:
    root = insert(root, num)

# 查找成功的平均查找长度
success_vals = [1, 2, 3, 4, 5, 6, 7]
success_avg_depth = get_avg_depth(root, success_vals)
print("查找成功的平均查找长度为", success_avg_depth)

# 查找失败的平均查找长度
fail_vals = [0, 8]
fail_avg_depth = get_avg_depth(root, fail_vals)
print("查找失败的平均查找长度为", fail_avg_depth)

输出结果为：

查找成功的平均查找长度为 2.857142857142857
查找失败的平均查找长度为 3.0