算法板子

发表于 分类于 阅读次数：

二分查找

二分查找为什么总是写错？_哔哩哔哩_bilibili

image-20260521135449487

例题：34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

注意边界问题

  1. 空数组问题：如果 nums = []，n = 0。循环不执行，binary_search_l 会检查 nums[0]，binary_search_r 会检查 nums[-1]，两者都会直接抛出 IndexError。
  2. target 大于数组中所有元素：例如 nums = [1, 2], target = 3。binary_search_l 循环结束后 right 会等于 n（即 2），此时检查 nums[right] 会抛出 IndexError。
  3. target 小于数组中所有元素：例如 nums = [1, 2], target = 0。binary_search_r 循环结束后 left 会等于 -1。在 Python 中 nums[-1] 不会报错而是取最后一个元素，这会导致逻辑错误（如果数组为空则依然会报错）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
def searchRange(nums: list[int], target: int) -> list[int]:
    n = len(nums)
    # 边界问题 1：提前处理空数组
    if n == 0:
        return [-1, -1]

    def binary_search_l(left, right, target):
        while left + 1 != right:
            mid = (left + right) // 2
            if nums[mid] < target:
                left = mid
            else:
                right = mid
        # 边界问题 2：right 可能越界到达 n，需要先判断 right != n
        if right != n and nums[right] == target:
            return right
        return -1

    def binary_search_r(left, right, target):
        while left + 1 != right:
            mid = (left + right) // 2
            if nums[mid] <= target:
                left = mid
            else:
                right = mid
        # 边界问题 3：left 可能越界到达 -1，需要先判断 left != -1
        if left != -1 and nums[left] == target:
            return left
        return -1

    # 寻找左边界
    left_idx = binary_search_l(-1, n, target)
    
    # 优化：如果左边界都找不到，说明 target 不存在，直接返回，无需再找右边界
    if left_idx == -1:
        return [-1, -1]
        
    # 寻找右边界（此时可以缩小左边界范围，从 left_idx - 1 开始找，提升微小性能）
    right_idx = binary_search_r(left_idx - 1, n, target)
    
    return [left_idx, right_idx]