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;}
};

---

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

对比维度	暴力枚举法	二分查找法
核心思想	遍历数组所有元素，记录第一个和最后一个匹配的位置。	通过两次二分查找分别定位左右边界，利用数组有序性快速缩小范围。
时间复杂度	O(n)（遍历所有元素）。	O(log n)（两次二分查找，每次时间复杂度为 O(log n)）。
空间复杂度	O(1)（无需额外存储）。	O(1)（仅需常数变量记录指针）。
实现方式	单层循环遍历数组，记录匹配的起始和结束索引。	两次独立的二分查找，分别处理左右边界。
适用场景	无序数组、小规模数据（n ≤ 100）。	有序数组、大规模数据（n ≥ 1e6）。
优点	实现简单，不依赖数组有序性。	时间复杂度极低，适合处理大规模数据。
缺点	数据规模大时性能极差（例如 n=1e6 时需 1e6 次操作）。	需处理二分查找的边界条件和中间值取整方向，实现复杂度较高。