二分查找（LeetCode 704）

题目来源：LeetCode 704 · 二分查找

题目

给定一个升序整数数组 nums 和目标值 target，返回 target 的下标；不存在则返回 -1。

思路

数组有序，所以不用从 0 逐个找，而是每次从中间猜：

1. 在区间 [left, right] 取中点 mid
2. nums[mid] < target → 目标在右半区，left = mid + 1
3. nums[mid] > target → 目标在左半区，right = mid - 1
4. 相等 → 命中；left > right → 不存在

每轮区间减半，最多 O(log n) 次结束。

动画演示

蓝色 left、绿色 right 夹出一个搜索区间，琥珀色 mid 是每次的猜测；被淘汰的格子会淡出。可以自定义数组和 target，用「下一步」单步观察指针如何收敛：

代码

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] < target:
                left = mid + 1
            elif nums[mid] > target:
                right = mid - 1
            else:
                return mid
        return -1

复杂度

• 时间：O(log n)，每轮搜索区间减半
• 空间：O(1)，只用了三个指针

易错点

• mid = left + (right - left) // 2 比 (left + right) // 2 安全——后者在 C++/Java 里可能溢出
• while left <= right 要带等号：left == right 时区间里还有一个元素，必须再比较一次，否则会漏判
• 移动左右指针时需要让 mid +1 或者 -1，因为已经能确定 mid 位置的值不是 target，并且这样能确保每次左右指针都至少移动一格，防止死循环