使用二分查找法在排序数组中查找目标值

二分查找是一种高效的查找算法，时间复杂度为 O(log n)。这里我将提供一个完整的实现，包括边界情况处理。

def binary_search(nums, target):
    """
    在排序数组 nums 中查找目标值 target

    参数:
        nums: 排序数组（升序）
        target: 要查找的目标值

    返回:
        如果找到目标值，返回其索引
        如果未找到目标值，返回 -1
    """
    if not nums:  # 处理空数组
        return -1

    left, right = 0, len(nums) - 1

    while left <= right:
        # 计算中间位置，防止整数溢出
        mid = left + (right - left) // 2

        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

def binary_search_recursive(nums, target, left=None, right=None):
    """
    二分查找的递归实现
    """
    if left is None:
        left = 0
    if right is None:
        right = len(nums) - 1

    if left > right:
        return -1

    mid = left + (right - left) // 2

    if nums[mid] == target:
        return mid
    elif nums[mid] < target:
        return binary_search_recursive(nums, target, mid + 1, right)
    else:
        return binary_search_recursive(nums, target, left, mid - 1)

# 测试代码
if __name__ == "__main__":
    # 测试用例
    test_cases = [
        ([1, 3, 5, 7, 9], 5, 2),      # 目标值在中间
        ([1, 3, 5, 7, 9], 1, 0),      # 目标值在开头
        ([1, 3, 5, 7, 9], 9, 4),      # 目标值在末尾
        ([1, 3, 5, 7, 9], 3, 1),      # 目标值在中间偏左
        ([1, 3, 5, 7, 9], 7, 3),      # 目标值在中间偏右
        ([1, 3, 5, 7, 9], 0, -1),     # 目标值小于所有元素
        ([1, 3, 5, 7, 9], 10, -1),    # 目标值大于所有元素
        ([1, 3, 5, 7, 9], 4, -1),     # 目标值不存在但在范围内
        ([], 5, -1),                  # 空数组
        ([5], 5, 0),                  # 只有一个元素，且匹配
        ([5], 3, -1),                 # 只有一个元素，不匹配
    ]

    print("测试迭代版本:")
    for nums, target, expected in test_cases:
        result = binary_search(nums, target)
        status = "✓" if result == expected else "✗"
        print(f"{status} nums={nums}, target={target}, result={result}, expected={expected}")

    print("\n测试递归版本:")
    for nums, target, expected in test_cases:
        result = binary_search_recursive(nums, target)
        status = "✓" if result == expected else "✗"
        print(f"{status} nums={nums}, target={target}, result={result}, expected={expected}")

算法说明

核心思想

二分查找通过不断将搜索范围减半来快速定位目标值。它要求数组必须是已排序的。

关键步骤

1. 初始化指针：设置左指针 left=0，右指针 right=len(nums)-1
2. 循环条件：当 left <= right 时继续查找
3. 计算中点：mid = left + (right - left) // 2（防止整数溢出）
4. 比较判断：
   • 如果 nums[mid] == target，找到目标，返回索引
   • 如果 nums[mid] < target，目标在右侧，更新 left = mid + 1
   • 如果 nums[mid] > target，目标在左侧，更新 right = mid - 1
5. 未找到：循环结束后返回 -1

时间复杂度

• O(log n)：每次迭代将搜索范围减半
• 空间复杂度：
  • 迭代版本：O(1)
  • 递归版本：O(log n)（递归调用栈）

注意事项

1. 数组必须是有序的（升序）
2. 使用 mid = left + (right - left) // 2 而不是 (left + right) // 2 可以防止整数溢出
3. 循环条件是 left <= right 而不是 left < right，确保能处理只有一个元素的情况

这个实现既简洁又高效，是处理有序数组查找问题的标准方法。

作者声明:本文包含人工智能生成内容。