题目信息

  • 平台：LeetCode
  • 题目：704. 二分查找
  • 难度：简单
  • 题目链接：二分查找

题目描述

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

初步思路

这道题就是二分查找的模板题，直接考察二分查找的基础写法。二分查找的核心在于区间的定义，也就是循环不变量原则。常见的写法有两种：

  1. 左闭右闭：[left, right]
  2. 左闭右开：[left, right)

两种写法都正确，关键在于要保持区间定义一致，不能混淆。

算法分析

  • 核心思想：利用数组有序的性质，每次排除一半不存在目标的区间，缩小搜索范围
  • 技巧要点：坚持循环不变量原则，根据区间定义决定循环条件和边界更新
  • 防止溢出：mid = left + (right - left) / 2 比 (left + right) / 2 更安全
  • 时间复杂度：O(log n)
  • 空间复杂度：O(1)

代码实现（C++）

写法一：左闭右闭区间 [left, right]

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
};

写法二：左闭右开区间 [left, right)

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return -1;
    }
};

测试用例

输入 输出 说明
nums = [-1,0,3,5,9,12], target = 9 4 9 在数组中，下标为 4
nums = [-1,0,3,5,9,12], target = 2 -1 2 不在数组中

总结与反思

二分查找看起来简单，但边界条件很容易写错。记住一句话：区间定义写循环，不变原则要坚持。

  • 如果是左闭右闭 [left, right]，那么 right 初始化为 size - 1，循环条件是 left <= right，right 更新为 mid - 1
  • 如果是左闭右开 [left, right)，那么 right 初始化为 size，循环条件是 left < right，right 更新为 mid

只要牢记这一点，二分查找就再也不会写错边界了！

后续练习

以下是二分查找相关的经典题目，留待后续练习补充：