Python 编写一个程序实现二分查找

Document 对象参考手册 Python3 实例

二分查找是一种高效的查找算法，适用于已排序的数组。它通过将数组分成两半来逐步缩小查找范围，直到找到目标元素或确定目标元素不存在。

实例

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

# 示例数组
arr = [1, 3, 5, 7, 9, 11, 13, 15]
target = 7

# 调用二分查找函数
result = binary_search(arr, target)

if result != -1:
    print(f"元素 {target} 在数组中的索引是 {result}")
else:
    print(f"元素 {target} 不在数组中")

代码解析：

  1. binary_search 函数接受两个参数：arr 是已排序的数组，target 是要查找的目标元素。
  2. low 和 high 分别表示当前查找范围的最低和最高索引。
  3. while 循环在 low 小于等于 high 时继续执行，表示查找范围仍然有效。
  4. mid 计算当前查找范围的中间索引。
  5. 如果 arr[mid] 等于 target，则返回 mid，表示找到了目标元素。
  6. 如果 arr[mid] 小于 target，则调整 low 为 mid + 1，表示目标元素在右半部分。
  7. 如果 arr[mid] 大于 target，则调整 high 为 mid - 1，表示目标元素在左半部分。
  8. 如果循环结束仍未找到目标元素，则返回 -1，表示目标元素不在数组中。

输出结果：

元素 7 在数组中的索引是 3

Document 对象参考手册 Python3 实例