在有序表中利用折半查找查找关键字并输出查找位置

折半查找（二分查找）是一种在有序表中查找关键字的算法，其基本思想是每次将查找区间缩小一半，直到找到目标元素或者区间为空为止。

假设我们要在一个有序表arr中查找关键字key，初始时查找区间为整个表，即[0, n-1]，其中n为表中元素个数。具体的查找过程如下：

1. 将查找区间的下标范围[left, right]初始化为[0, n-1]。
2. 计算区间中间位置mid，即mid = (left + right) / 2。
3. 如果arr[mid]等于key，则查找成功，返回mid。
4. 如果arr[mid]大于key，则说明key可能在左半边，将查找区间缩小为[left, mid-1]。
5. 如果arr[mid]小于key，则说明key可能在右半边，将查找区间缩小为[mid+1, right]。
6. 重复步骤2~5，直到找到目标元素或者区间为空为止。

下面是一个示例代码实现：

def binary_search(arr, key):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == key:
            return mid
        elif arr[mid] > key:
            right = mid - 1
        else:
            left = mid + 1
    return -1  # 没有找到目标元素

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
key = 5
pos = binary_search(arr, key)
print("关键字位置：", pos)

输出结果为：

关键字位置： 4

说明在有序表arr中，关键字5位于下标为4的位置。