请写出对具有n个元素的有序表进行二分查找的算法

二分查找，也称为折半查找，是一种在有序数组中快速查找特定元素的搜索算法。其基本思想每次比较中间元素与目标值，然后根据比较结果决定是在左半部分、右半部分还是直接找到。以下是二分查找的伪代码：

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
            
    return -1  # 如果找不到，返回-1表示目标不存在于数组中

# 使用示例
arr = [1, 2, 3, 4, 5, 6, 7]
target = 5
result = binary_search(arr, target)
if result != -1:
    print(f"元素 {target} 的索引为：{result}")
else:
    print(f"{target} 不在数组中")

这个算法的时间复杂度是 O(log n)，因为它每次将查找范围减半。

相关问题

用c++写给出在一个递增有序表A中采用二分查找算法查找值为x的元素的递归算法

好的，下面是用C++实现的递归二分查找算法：

int binary_search(int A[], int left, int right, int x) {
    if (left > right) {
        return -1; // 如果left>right，说明找不到，返回-1
    }
    int mid = (left + right) / 2;
    if (A[mid] == x) {
        return mid; // 找到了，返回下标
    } else if (A[mid] > x) {
        return binary_search(A, left, mid - 1, x); // 在左边继续查找
    } else {
        return binary_search(A, mid + 1, right, x); // 在右边继续查找
    }
}

其中，`A`是递增有序表，`left`和`right`表示要查找的范围（初始时为`0`和`n-1`，其中`n`是数组长度），`x`是要查找的元素值。如果找到了，返回该元素在数组中的下标，否则返回`-1`表示未找到。

对关键字序列{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

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