二分查找

先定义区间

这里采用左闭右闭区间 [left, right]。这意味着左右端点都可能是答案，因此循环条件必须写成 left <= right。

def search(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

为什么是 mid ± 1

判断完 nums[mid] 后，已经确定它不是答案。新的搜索区间不应该再次包含 mid，所以向右时从 mid + 1 开始，向左时到 mid - 1 结束。

检查清单

1. 数组是否有序；
2. 搜索区间是闭区间还是半开区间；
3. 循环条件是否与区间定义一致；
4. 更新边界后，区间是否确实缩小。

只要这四件事前后一致，二分就不需要靠背模板。