第 23 课·搜索算法进阶

二分查找变体

lower-boundupper-boundbisect

第23课 - 二分查找变体

1. 学习目标

  • 理解三种二分查找变体：掌握 lower_bound（下界）、upper_bound（上界）和 bisect（二分插入点）的核心思想
  • 掌握实现方法：能够独立编写基于二分查找的边界查找函数
  • 学会应用场景：识别并应用边界查找解决实际问题（如统计元素出现次数、寻找插入位置等）
  • 熟练使用标准库：熟练运用 Python 的 bisect 模块高效解决问题

2. 核心概念

基础回顾

标准二分查找告诉我们目标值是否存在，但有时我们需要更多信息：

  • 目标值第一次出现的位置？
  • 目标值最后一次出现的位置？
  • 目标值如果不存在，应该插入到哪里？

这就是二分查找变体要解决的问题。

三种变体解析

lower_bound（下界）

通俗解释：在有序数组中找到第一个大于或等于目标值的位置。

想象在电影院找座位：票上写的是“第5排”，你需要找到第一个空闲或可用的第5排座位。

def lower_bound(nums, target):
    # 返回第一个 >= target 的位置
    left, right = 0, len(nums)
    while left < right:
        mid = (left + right) // 2
        if nums[mid] < target:
            left = mid + 1  # 目标值在右半部分
        else:
            right = mid     # 可能是答案，继续向左搜索
    return left

upper_bound（上界）

通俗解释：在有序数组中找到第一个严格大于目标值的位置。

继续电影院的例子：现在要找第一个完全不在第5排的座位（即第6排或更后排的开始）。

def upper_bound(nums, target):
    # 返回第一个 > target 的位置
    left, right = 0, len(nums)
    while left < right:
        mid = (left + right) // 2
        if nums[mid] <= target:
            left = mid + 1  # 包含等于时，也要向右找
        else:
            right = mid
    return left

bisect（二分插入点）

通俗解释：结合下界和上界，决定元素插入位置以保持数组有序。

Python 的 bisect 模块提供了两个核心函数：

  • bisect_left：等同于 lower_bound
  • bisect_right：等同于 upper_bound
import bisect

# 示例：在数组中查找
nums = [1, 2, 2, 2, 3]
target = 2

# 查找下界（第一个 >= 2 的位置）
pos_left = bisect.bisect_left(nums, target)  # 输出: 1

# 查找上界（第一个 > 2 的位置）
pos_right = bisect.bisect_right(nums, target)  # 输出: 4

关键区别图示

数组: [1, 2, 2, 2, 3, 4]
目标值: 2

lower_bound: 位置 1 (第一个2的位置)
upper_bound: 位置 4 (最后一个2的下一个位置)
目标值2的范围: [1, 4) 左闭右开区间

3. 代码示例

from bisect import bisect_left, bisect_right

def count_occurrences(nums, target):
    """使用二分查找变体统计目标值出现次数"""
    # 找到第一个出现位置
    left_index = bisect_left(nums, target)
    
    # 如果目标不存在，返回0
    if left_index == len(nums) or nums[left_index] != target:
        return 0
    
    # 找到最后一个出现位置的下一个位置
    right_index = bisect_right(nums, target)
    
    # 出现次数 = 右边界 - 左边界
    return right_index - left_index

def find_insert_position(nums, target):
    """找到元素应该插入的位置，保持数组有序"""
    return bisect_left(nums, target)

def find_first_and_last(nums, target):
    """找到目标值的第一次和最后一次出现的位置"""
    left = bisect_left(nums, target)
    right = bisect_right(nums, target) - 1
    
    if left <= right and nums[left] == target:
        return (left, right)
    return (-1, -1)

# 测试示例
if __name__ == "__main__":
    nums = [1, 2, 2, 2, 3, 4, 5]
    target = 2
    
    print(f"数组: {nums}")
    print(f"目标值: {target}")
    print(f"出现次数: {count_occurrences(nums, target)}")
    print(f"插入位置: {find_insert_position(nums, target)}")
    
    first, last = find_first_and_last(nums, target)
    print(f"第一次出现: 索引{first}, 最后一次出现: 索引{last}")
    
    # 测试目标值不存在的情况
    target_missing = 6
    print(f"\n目标值 {target_missing} 出现次数: {count_occurrences(nums, target_missing)}")
    print(f"目标值 {target_missing} 插入位置: {find_insert_position(nums, target_missing)}")

输出结果：

数组: [1, 2, 2, 2, 3, 4, 5]
目标值: 2
出现次数: 3
插入位置: 1
第一次出现: 索引1, 最后一次出现: 索引3

目标值 6 出现次数: 0
目标值 6 插入位置: 7

4. 实践练习

练习1：寻找插入位置（简单）

题目：给定一个排序数组和一个目标值，返回目标值应该插入的位置，使得数组仍然有序。

def search_insert(nums, target):
    # 你的代码在这里
    pass

# 测试用例
print(search_insert([1, 3, 5, 6], 5))  # 输出: 2
print(search_insert([1, 3, 5, 6], 2))  # 输出: 1
print(search_insert([1, 3, 5, 6], 7))  # 输出: 4
print(search_insert([1, 3, 5, 6], 0))  # 输出: 0

练习2：统计元素出现次数（中等）

题目：给定一个排序数组和一个目标值，统计目标值在数组中出现的次数。要求时间复杂度为 O(log n)。

def count_target(nums, target):
    # 你的代码在这里
    pass

# 测试用例
print(count_target([5, 7, 7, 8, 8, 10], 8))   # 输出: 2
print(count_target([5, 7, 7, 8, 8, 10], 6))   # 输出: 0
print(count_target([2, 2, 2, 2, 2], 2))       # 输出: 5

练习3：寻找第一个错误版本（挑战）

题目：假设你有多个版本的代码 [1, 2, ..., n]，其中从某个版本开始出现错误。给定一个函数 isBadVersion(version) 判断某个版本是否错误，找到第一个错误的版本。

# 假设的API
def isBadVersion(version):
    # 模拟：从版本4开始都是错误的
    return version >= 4

def first_bad_version(n):
    # 你的代码在这里
    pass

# 测试用例
print(first_bad_version(5))  # 输出: 4
print(first_bad_version(10)) # 输出: 4

5. 常见错误

错误1：混淆下界和上界

# 错误写法：当目标存在时，upper_bound返回的是最后一个匹配元素的下一个位置
# 误以为upper_bound直接返回最后一个匹配位置
last_pos = upper_bound(nums, target)  # 这是错误的！

# 正确写法：
last_pos = upper_bound(nums, target) - 1  # 需要减1

错误2：返回值索引越界

# 错误：未检查索引有效性
def find_target(nums, target):
    index = lower_bound(nums, target)
    return nums[index]  # 可能越界！当target > 所有元素时

# 正确：先检查边界
def find_target(nums, target):
    index = lower_bound(nums, target)
    if index < len(nums) and nums[index] == target:
        return nums[index]
    return None  # 或抛出异常

错误3：循环条件设置错误

# 错误：使用 left <= right 会导致死循环
while left <= right:
    # 对于变体查找，通常使用 left < right
    # 因为变体查找的是边界，而不是确切元素
    
# 正确：
while left < right:
    mid = (left + right) // 2
    # 注意更新逻辑的细微差别

错误4：忘记处理空数组

# 错误：未检查空数组情况
def lower_bound(nums, target):
    left, right = 0, len(nums)
    # 当nums为空时，len(nums)=0，right=0
    while left < right:  # 0 < 0 为False，不会进入循环
        # 这是正确的处理
    return left  # 返回0

6. 小结

关键要点回顾

  1. 三种变体核心区别：

    • lower_bound：找第一个 ≥ target 的位置
    • upper_bound：找第一个 > target 的位置
    • bisect：结合两者，确定插入位置或统计范围

  2. 重要公式：

    • 元素出现次数 = upper_bound(target) - lower_bound(target)
    • 插入位置 = lower_bound(target)
    • 最后一个出现位置 = upper_bound(target) - 1

  3. Python 标准库：

    • bisect.bisect_left 等价于 lower_bound
    • bisect.bisect_right 等价于 upper_bound
    • bisect.insort 可以在保持有序的情况下插入元素

  4. 应用场景：

    • 统计有序数组中元素出现次数
    • 查找元素的插入位置
    • 解决区间查询问题
    • 处理旋转排序数组等变种问题

与上下文关联

  • 上接：第22课的基础二分查找，需要理解标准二分查找的原理
  • 下启：第24课的插值搜索，将在二分查找的基础上学习如何优化搜索策略

进阶思考

当你完全掌握这些变体后，可以尝试解决：

  1. 在旋转排序数组中查找元素
  2. 查找元素在排序数组中的第一个和最后一个位置（LeetCode 34题）
  3. 在排序数组中查找元素的第一个和最后一个位置的变种问题

掌握二分查找变体是解决复杂搜索问题的关键钥匙！

练习编辑器

rust
Loading...

继续学习

完成本课后，建议继续学习下一课「插值搜索」 以巩固所学知识。