3.2 二分查找专题：LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置

1. 题目链接

LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置

2. 题目描述

给定一个升序排列的整数数组 nums 和一个目标值 target，返回目标值在数组中的起始位置和结束位置。若不存在，返回 [-1, -1]。
要求：时间复杂度为 O(log n)。

3. 示例分析

示例1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]（第一个 8 在索引 3，最后一个在索引 4）。

示例2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]（6 不存在）。

暴力枚举法：遍历数组，记录第一个和最后一个匹配的位置。
二分查找法：通过两次二分查找分别定位左右边界。

4. 算法思路

两次二分查找法：

1. 寻找左边界：

   • 初始化 left = 0, right = nums.size() - 1。
   • 循环条件 left < right，中间值 mid 向左取整（mid = left + (right - left) / 2）。
   • 若 nums[mid] >= target，压缩右边界 right = mid，否则增大左边界 left = mid + 1。
   • 最终 left 指向左边界，需检查是否等于 target。

2. 寻找右边界：

   • 初始化 left = 0, right = nums.size() - 1。
   • 循环条件 left < right，中间值 mid 向右取整（mid = left + (right - left + 1) / 2）。
   • 若 nums[mid] <= target，压缩左边界 left = mid，否则减小右边界 right = mid - 1。
   • 最终 left 指向右边界，需检查是否等于 target。

5. 边界条件与注意事项

1. 空数组处理：直接返回 [-1, -1]。
2. 越界检查：左边界需验证 left < nums.size()，右边界需验证 right >= 0。
3. 中间值取整方向：
   • 左边界查找时，mid 向左取整避免死循环。
   • 右边界查找时，mid 向右取整确保收缩正确性。
4. 重复元素处理：需确保找到第一个和最后一个匹配位置。

6. 代码实现

class Solution 
{
public:
    vector<int> searchRange(vector<int>& nums, int target) 
    {
     	if (nums.empty()) return {-1, -1};
        int left = 0, right = nums.size() - 1;
        vector<int> ret;
        // 1.左边 target 第一次出现
        while(left < right)
        {
            int mid = left + (right - left) / 2; // 取左边
            if(nums[mid] >= target) right = mid;// 关键条件：压缩右边界
            else left = mid + 1;
        }
        ret.push_back((left < nums.size() && nums[left] == target) ? left : -1);
        // 2.右边 target 第一次出现
        left = 0, right = nums.size() - 1;
        while (left < right) 
        {
            int mid = left + (right - left + 1) / 2; // 取右边
            if (nums[mid] <= target) left = mid; // 关键条件：压缩左边界
            else right = mid - 1;
        }
        ret.push_back((right >= 0 && nums[left] == target) ? right : -1);

        return ret;
    }
};

暴力枚举法与二分查找法对比图表