二分查找算法初阶：LeetCode 实战解析

查找元素的第一个和最后一个位置

题目描述

在非递减顺序排列的整数数组 nums 中，找出目标值 target 的开始位置和结束位置。不存在则返回 [-1, -1]。要求时间复杂度 O(log n)。

思路分析

这道题是典型的二分区间应用。我们需要分别找到左边界和右边界。由于数组可能包含重复元素，不能简单使用基础二分模板，需明确区间特性。

找左边界：

• 左区间 [left, k - 1] 均小于 target。
• 右区间 [k, right] 均大于等于 target。
• 当 nums[mid] < target 时，[left, mid] 可舍弃，left = mid + 1。
• 当 nums[mid] >= target 时，mid 可能是答案，不可舍弃，right = mid。
• 注意：此处取整应向下，避免死循环。

找右边界：

• 左区间 [left, k] 均小于等于 target。
• 右区间 [k + 1, right] 均大于 target。
• 当 nums[mid] <= target 时，mid 可能是答案，left = mid。
• 当 nums[mid] > target 时，[mid, right] 可舍弃，right = mid - 1。
• 注意：此处取整应向上，通常写作 mid = left + (right - left + 1) / 2。

代码实现

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int n = nums.size();
        if (n == 0) return {-1, -1};

        // 找左边界
        int left = 0, right = n - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        int Left = (nums[left] != target) ? -1 : left;

        // 找右边界
        left = 0; right = n - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (nums[mid] <= target) left = mid;
            else right = mid - 1;
        }
        int Right = (nums[left] != target) ? -1 : left;

        return {Left, Right};
    }
};

小技巧：如果 while 循环中有 -1（即 right = mid - 1），取整建议用向下取整；如果没有 -1（即 right = mid），建议用向上取整，以防止死循环。

搜索插入位置

题目描述

给定排序数组和目标值，找到目标值索引。若不存在，返回其应插入的位置。要求 O(log n)。

思路分析

这本质上是寻找'大于等于目标值的最左端'。可以复用上述左边界查找的逻辑。如果所有元素都小于目标值，则插入到末尾。

代码实现

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int ret = -1;
        int left = 0, right = nums.size() - 1;
        
        // 边界情况：目标值比所有元素都大
        if (nums[nums.size() - 1] < target) return nums.size();

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

另一种写法是直接记录满足条件的最小下标：

class Solution {
public:
    int searchInsert(vector<int>& a, int value) {
        int L = 0, R = a.size() - 1;
        int index = -1;
        while (L <= R) {
            int mid = L + ((R - L + 1) >> 1);
            if (a[mid] >= value) {
                index = mid;
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
        return (index == -1) ? R + 1 : index;
    }
};

x 的平方根

题目描述

计算非负整数 x 的算术平方根，结果只保留整数部分。不允许使用内置指数函数。

思路分析

求 sqrt(x) 等价于寻找最大的整数 k，使得 k * k <= x。这是一个典型的二分答案问题。由于 x 可能很大，计算 mid * mid 时需使用 long long 防止溢出。

代码实现

class Solution {
public:
    int mySqrt(int x) {
        if (x < 1) return 0;
        int left = 1, right = x;
        while (left < right) {
            // 向上取整，配合 left = mid
            long long mid = left + (right - left + 1) / 2;
            if (mid * mid <= x) left = mid;
            else right = mid - 1;
        }
        return left;
    }
};

或者使用记录答案的方式：

class Solution {
public:
    int mySqrt(int x) {
        if (x < 1) return 0;
        int left = 1, right = x;
        int index = -1;
        while (left <= right) {
            long long mid = left + (right - left + 1) / 2;
            if (mid * mid <= x) {
                index = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return index;
    }
};

通过这几道经典例题，可以看出二分查找的核心在于确定区间性质以及更新指针时的取整策略。掌握这些细节，就能有效避免死循环并正确求解各类变体问题。