对关键字序列{21，34，56，78，99，100，102，109，200} 分别进行折半查找109，20。 请选择： 1. 根据算法步骤写出查找过程，列举查找过程中带查找序列和上限下限，中间值并画出有序表进行二分查找的判定树。 2. 编程实现查找过程和结果并画出有序表进行二分查找的判定树。 注意：1和2中请选择一个方式进行查找算法练习。

1. 折半查找的算法步骤如下：

- 将待查找序列按照关键字大小升序排列。
- 初始化上限`high`为序列末尾的下标，下限`low`为序列开头的下标。
- 当`low<=high`时，重复以下步骤：
- 计算中间位置`mid=(low+high)/2`。
- 如果待查找关键字等于中间位置的关键字，则返回该位置。
- 如果待查找关键字小于中间位置的关键字，则在上半部分继续查找，将`high`更新为`mid-1`。
- 如果待查找关键字大于中间位置的关键字，则在下半部分继续查找，将`low`更新为`mid+1`。
- 如果待查找关键字不在序列中，则返回不存在的标记。

对于关键字序列{21，34，56，78，99，100，102，109，200}，折半查找109的过程如下：

- 初始时，`low=0`，`high=8`，`mid=(0+8)/2=4`。
- 中间位置的关键字为99，109大于99，故在上半部分继续查找。
- 更新`high=mid-1=3`，`mid=(0+3)/2=1`。
- 中间位置的关键字为34，109大于34，故在上半部分继续查找。
- 更新`high=mid-1=0`，`mid=(0+0)/2=0`。
- 中间位置的关键字为21，109大于21，故在上半部分继续查找。
- 更新`high=mid-1=-1`，退出查找。109在序列中，返回该位置3。

折半查找20的过程如下：

- 初始时，`low=0`，`high=8`，`mid=(0+8)/2=4`。
- 中间位置的关键字为99，20小于99，故在下半部分继续查找。
- 更新`low=mid+1=5`，`high=8`，`mid=(5+8)/2=6`。
- 中间位置的关键字为102，20小于102，故在下半部分继续查找。
- 更新`low=mid+1=7`，`high=8`，`mid=(7+8)/2=7`。
- 中间位置的关键字为109，20小于109，故在下半部分继续查找。
- 更新`low=mid+1=8`，退出查找。20不在序列中，返回不存在的标记。

2. 以下是Python语言实现折半查找的代码，以及查找过程的判定树。在代码中，使用了递归方式实现查找过程。

def binarySearch(seq, low, high, key):
    if low > high:
        return -1 # 不存在
    mid = (low + high) // 2
    if seq[mid] == key:
        return mid # 找到关键字
    elif seq[mid] > key:
        return binarySearch(seq, low, mid-1, key) # 在下半部分查找
    else:
        return binarySearch(seq, mid+1, high, key) # 在上半部分查找

seq = [21, 34, 56, 78, 99, 100, 102, 109, 200]
key1 = 109
key2 = 20

print("查找{}的结果：{}".format(key1, binarySearch(seq, 0, len(seq)-1, key1)))
print("查找{}的结果：{}".format(key2, binarySearch(seq, 0, len(seq)-1, key2)))

判定树如下：

      99
     /  \
    /    \
  34      102
 /  \     /  \
/    \   /    \
21    56 100  109
      /         \
     /           \
    78          200

在判定树中，每个非叶子节点都表示一次比较操作。从根节点开始，如果待查找关键字小于节点的关键字，则向左子树查找；如果待查找关键字大于节点的关键字，则向右子树查找。叶子节点表示查找结束时的结果。