Python二分查找案例如何精准查找

本文目录导读：

1. 基础二分查找（精准查找）
2. 查找边界值（精准定位）
3. 查找近似值（最接近目标）
4. 实际应用案例
5. 性能优化版本
6. 通用二分查找模板
7. 注意事项

我来给你介绍Python二分查找的精准实现方法,包括基础版本和多种实用案例。

基础二分查找（精准查找）

标准实现

def binary_search(arr, target):
    """
    精准二分查找，返回目标值的索引
    如果不存在，返回-1
    """
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2  # 防止整数溢出
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1  # 未找到
# 测试
arr = [1, 3, 5, 7, 9, 11, 13, 15]
print(binary_search(arr, 7))   # 输出: 3
print(binary_search(arr, 8))   # 输出: -1

查找边界值（精准定位）

查找第一个等于target的位置

def find_first_equal(arr, target):
    """查找第一个等于target的元素索引"""
    left, right = 0, len(arr) - 1
    result = -1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            result = mid      # 记录当前位置
            right = mid - 1   # 继续向左查找
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return result
# 测试
arr = [1, 2, 2, 2, 3, 4, 5]
print(find_first_equal(arr, 2))  # 输出: 1

查找最后一个等于target的位置

def find_last_equal(arr, target):
    """查找最后一个等于target的元素索引"""
    left, right = 0, len(arr) - 1
    result = -1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            result = mid      # 记录当前位置
            left = mid + 1    # 继续向右查找
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return result
# 测试
arr = [1, 2, 2, 2, 3, 4, 5]
print(find_last_equal(arr, 2))  # 输出: 3

查找近似值（最接近目标）

查找最接近target的元素

def find_closest(arr, target):
    """查找最接近target的元素索引"""
    if not arr:
        return -1
    left, right = 0, len(arr) - 1
    # 边界情况处理
    if target <= arr[left]:
        return left
    if target >= arr[right]:
        return right
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    # 比较两个最接近的元素
    if abs(arr[left] - target) <= abs(arr[left + 1] - target):
        return left
    else:
        return left + 1
# 测试
arr = [1, 3, 5, 7, 9, 11]
print(find_closest(arr, 6))   # 输出: 2 (值5)
print(find_closest(arr, 8))   # 输出: 3 (值7)

实际应用案例

案例1：查找插入位置

def search_insert(nums, target):
    """
    LeetCode 35: 搜索插入位置
    返回target应该插入的索引位置
    """
    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 left
# 测试
nums = [1, 3, 5, 6]
print(search_insert(nums, 5))  # 输出: 2
print(search_insert(nums, 2))  # 输出: 1
print(search_insert(nums, 7))  # 输出: 4

案例2：旋转数组查找

def search_rotated(nums, target):
    """
    LeetCode 33: 搜索旋转排序数组
    """
    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
        # 判断哪部分是有序的
        if nums[left] <= nums[mid]:  # 左半部分有序
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:  # 右半部分有序
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1
# 测试
nums = [4, 5, 6, 7, 0, 1, 2]
print(search_rotated(nums, 0))  # 输出: 4
print(search_rotated(nums, 3))  # 输出: -1

案例3：求平方根

def my_sqrt(x):
    """
    LeetCode 69: x的平方根
    返回整数部分
    """
    if x == 0 or x == 1:
        return x
    left, right = 1, x
    while left <= right:
        mid = left + (right - left) // 2
        if mid * mid == x:
            return mid
        elif mid * mid < x:
            left = mid + 1
        else:
            right = mid - 1
    return right
# 测试
print(my_sqrt(8))   # 输出: 2
print(my_sqrt(16))  # 输出: 4

性能优化版本

使用bisect模块（Python内置）

import bisect
# bisect_left: 查找第一个大于等于target的位置
# bisect_right: 查找第一个大于target的位置
arr = [1, 2, 2, 2, 3, 4, 5]
# 查找等于target的范围
left_idx = bisect.bisect_left(arr, 2)   # 第一个2的位置
right_idx = bisect.bisect_right(arr, 2)  # 最后一个2的下一个位置
print(f"2的范围: [{left_idx}, {right_idx-1}]")  # 输出: [1, 3]

通用二分查找模板

def binary_search_template(nums, target):
    """
    通用二分查找模板
    """
    left, right = 0, len(nums) - 1
    while left + 1 < right:  # 当区间长度>2时
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid
        else:
            right = mid
    # 最后检查两个元素
    if nums[left] == target:
        return left
    if nums[right] == target:
        return right
    return -1
# 测试
arr = [1, 3, 5, 7, 9, 11, 13, 15]
print(binary_search_template(arr, 7))   # 输出: 3

注意事项

1. 边界条件：确保left <= right正确使用
2. 中点计算：使用 left + (right - left) // 2 避免整数溢出
3. 循环终止：确保最终能退出循环
4. 数组有序：二分查找要求数组有序
5. 重复元素：注意处理重复元素的情况

这些案例覆盖了大多数二分查找的应用场景,可以根据具体需求选择合适的实现方式。