LeetCode 704. 二分查找

◎

本节目标

用左闭右闭搜索区间完成有序数组中的精确查找。

这道题是二分查找解题框架的起点：在升序数组中寻找目标值，找不到时返回 -1。

查看原题

题意与约束

数组 nums 按严格递增顺序排列。需要返回 target 的下标；目标不存在则返回 -1。

朴素思路与瓶颈

从左到右逐个比较一定能找到目标，但最坏要检查全部 n 个元素。严格递增意味着一次中点比较就能排除不可能的一半，因而应使用 O(log n) 的二分查找。

左闭右闭区间

令搜索区间为 [left, right]。每次循环开始时，若 target 存在，它仍在这个闭区间里：

• nums[mid] < target 时，中点和左侧都太小，令 left = mid + 1；
• nums[mid] > target 时，中点和右侧都太大，令 right = mid - 1；
• 相等时直接得到答案。

因此每次排除的部分都不可能含有目标，循环结束时 left > right 才能断言目标不存在。

代码实现

两份实现都用 left + (right - left) / 2 计算中点，避免直接相加的溢出风险。

C++

C++17

#include <vector>
using namespace std;

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = static_cast<int>(nums.size()) - 1;

        while (left <= right) {
            const int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
};

Python

Python 3

class Solution:
    def search(self, nums, target):
        left = 0
        right = 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

复杂度分析

• 时间复杂度：O(log n)。
• 空间复杂度：O(1)。

易错点

• 空数组时 right = -1，循环不会进入，正确返回 -1。
• 闭区间要配合 left <= right，不能误写成 <。
• 更新必须越过 mid，否则区间可能不缩小。

模式迁移

从“找一个相等值”继续推广，就得到查找第一个满足条件的位置；下一题会用它组合出目标的首尾边界。