实用指南：Leetcode 59 二分搜索

1 题目

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

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

提示：

0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109

2 代码实现

using namespace std ;
class Solution {
public:int left_bound(vector& nums ,int target){int left = 0 , right = nums.size() - 1 ;while (left <= right ){int mid = left + (right - left ) / 2 ;if (nums[mid] < target ){left = mid + 1 ;}else if (nums[mid] > target){right = mid - 1 ;}else if (nums[mid] == target){right = mid - 1 ;}}if (left < 0 || left >= nums.size() || nums[left] != target){return -1 ;}return left ;}int right_bound(vector& nums ,int target){int left = 0 , right = nums.size() - 1 ;while (left <= right ){int mid = left + (right - left ) / 2 ;if (nums[mid] < target ){left = mid + 1 ;}else if (nums[mid] > target){right = mid - 1 ;}else if (nums[mid] == target){left = mid + 1 ;}}if (right < 0 || right >= nums.size() || nums[right] != target){return -1 ;}return right ;}vector searchRange(vector& nums, int target) {int left = left_bound(nums,target);int right = right_bound(nums,target);return{left , right};}
};

题解

一、题目分析

1. 题目核心要求

输入：非递减（升序）整数数组 nums + 目标值 target
输出：target 在数组中首次出现的索引和最后出现的索引；若不存在则返回 [-1, -1]
约束：时间复杂度必须为 O(log n)（直接排除暴力遍历 O(n) 解法）

2. 关键特征

数组有序：非递减排列是二分搜索的前提，可通过中间元素快速缩小查找范围
元素可重复：这是本题与「标准二分查找」的核心区别 —— 标准二分找到目标后直接返回，本题需找到「边界」（首次 / 末次出现位置）
边界场景多：需处理空数组、目标在数组外（小于所有元素 / 大于所有元素）、目标是唯一元素等极端情况

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 不在数组中，返回默认值
示例 3：nums = [], target=0 → 输出 [-1,-1]空数组无目标元素，返回默认值

二、解题思路

1. 核心思想：二分搜索找边界

由于要求 O(log n) 时间复杂度，只能用二分搜索。本题的关键是将「找起始 + 结束位置」拆分为两个子问题：

找 target 的左边界：首次出现的索引（最小的 index 满足 nums[index] == target）
找 target 的右边界：末次出现的索引（最大的 index 满足 nums[index] == target）

2. 二分搜索的范式选择

本题采用「左闭右闭 [left, right]」范式（你提供的代码风格），该范式的核心特点：

初始边界：left=0，right = nums.size()-1（左右指针均指向有效元素）
循环条件：left <= right（当 left == right 时，区间 [left, right] 仍有一个元素待检查）
指针更新：找到无效元素后，直接排除当前 mid（left=mid+1 或 right=mid-1），确保区间严格缩小

3. 左边界查找逻辑（`left_bound` 函数）

目标：找到「第一个等于 target 的元素索引」，核心是「找到目标后不返回，继续向左收缩范围」：

当 nums[mid] < target：target 在 mid 右侧，left=mid+1（排除 mid 及左侧）
当 nums[mid] > target：target 在 mid 左侧，right=mid-1（排除 mid 及右侧）
当 nums[mid] == target：mid 可能是左边界，但左侧可能还有更靠前的 target，因此 right=mid-1（收缩右边界，继续向左查找）
循环终止后：left 是潜在左边界，需检查是否越界 + 是否等于 target

4. 右边界查找逻辑（`right_bound` 函数）

目标：找到「最后一个等于 target 的元素索引」，核心是「找到目标后不返回，继续向右收缩范围」：

当 nums[mid] < target：target 在 mid 右侧，left=mid+1（排除 mid 及左侧）
当 nums[mid] > target：target 在 mid 左侧，right=mid-1（排除 mid 及右侧）
当 nums[mid] == target：mid 可能是右边界，但右侧可能还有更靠后的 target，因此 left=mid+1（收缩左边界，继续向右查找）
循环终止后：right 是潜在右边界，需检查是否越界 + 是否等于 target

5. 整体流程

调用 left_bound 得到左边界 left_idx
调用 right_bound 得到右边界 right_idx
返回 [left_idx, right_idx]（若目标不存在，两者均为 -1，符合题目要求）

三、完整代码（带详细注释）

// 引入 std 命名空间，简化代码（LeetCode 环境默认支持）
using namespace std;
class Solution {
public:// 查找 target 的左边界（首次出现的索引），不存在返回 -1int left_bound(vector& nums, int target) {int left = 0;                  // 左指针初始指向数组开头int right = nums.size() - 1;   // 右指针初始指向数组末尾（左闭右闭范式）// 循环条件：left <= right（区间非空，仍有元素待检查）while (left <= right) {// 计算 mid：避免 (left+right) 溢出的安全写法，等价于 (left+right)/2int mid = left + (right - left) / 2;if (nums[mid] < target) {// target 在 mid 右侧，排除 mid 及左侧，左指针右移left = mid + 1;} else if (nums[mid] > target) {// target 在 mid 左侧，排除 mid 及右侧，右指针左移right = mid - 1;} else if (nums[mid] == target) {// 找到 target，但可能不是左边界，收缩右边界继续向左找right = mid - 1;}}// 循环终止后，检查 left 是否为有效左边界：// 1. left 越界（<0 或 >=nums.size()）→ 目标不存在// 2. nums[left] != target → 目标不存在（如 nums=[1,3,5], target=2，left=1 但 nums[1]=3≠2）if (left < 0 || left >= nums.size() || nums[left] != target) {return -1;}// 以上条件均不满足，left 即为左边界return left;}// 查找 target 的右边界（末次出现的索引），不存在返回 -1int right_bound(vector& nums, int target) {int left = 0;                  // 左指针初始指向数组开头int right = nums.size() - 1;   // 右指针初始指向数组末尾（左闭右闭范式）// 循环条件：left <= right（区间非空，仍有元素待检查）while (left <= right) {// 安全计算 mid，避免溢出int mid = left + (right - left) / 2;if (nums[mid] < target) {// target 在 mid 右侧，排除 mid 及左侧，左指针右移left = mid + 1;} else if (nums[mid] > target) {// target 在 mid 左侧，排除 mid 及右侧，右指针左移right = mid - 1;} else if (nums[mid] == target) {// 找到 target，但可能不是右边界，收缩左边界继续向右找left = mid + 1;}}// 循环终止后，检查 right 是否为有效右边界：// 1. right 越界（<0 或 >=nums.size()）→ 目标不存在// 2. nums[right] != target → 目标不存在（如 nums=[1,3,5], target=4，right=2 但 nums[2]=5≠4）if (right < 0 || right >= nums.size() || nums[right] != target) {return -1;}// 以上条件均不满足，right 即为右边界return right;}// 本题核心函数：组合左边界和右边界，返回结果vector searchRange(vector& nums, int target) {int left_idx = left_bound(nums, target);  // 获取左边界int right_idx = right_bound(nums, target); // 获取右边界return {left_idx, right_idx};             // 返回结果数组}
};

四、关键细节拆解（避坑指南）

1. mid 计算的溢出问题

为什么用 mid = left + (right - left)/2 而非 (left+right)/2？

当 left 和 right 接近 int 最大值（如 2^31-1）时，left+right 会超出 int 范围（溢出），导致数值错乱
优化写法先算 right-left（结果一定小于 right，不会溢出），再除以 2，最后加 left，保证计算安全

2. 左边界的循环终止后检查

循环终止时 left > right，为什么用 left 作为潜在左边界？

例：nums=[5,7,7,8,8,10], target=8
- 最后一次循环：left=3, right=3，mid=3（nums[3]=8），执行 right=2
- 循环终止：left=3 > right=2，left 恰好是首次出现的索引 3
本质：right 收缩到左边界左侧，left 最终停在左边界上

3. 右边界的循环终止后检查

循环终止时 left > right，为什么用 right 作为潜在右边界？

例：nums=[5,7,7,8,8,10], target=8
- 最后一次循环：left=4, right=4，mid=4（nums[4]=8），执行 left=5
- 循环终止：left=5 > right=4，right 恰好是末次出现的索引 4
本质：left 扩张到右边界右侧，right 最终停在右边界上

4. 边界检查的必要性

为什么必须检查 nums[left] == target 或 nums[right] == target？

反例：nums=[1,3,5], target=2
- 左边界查找：mid=1（nums[1]=3>2）→ right=0；mid=0（nums[0]=1<2）→ left=1；循环终止 left=1>right=0
- 此时 left=1 在数组范围内，但 nums[1]=3≠2，若不检查会误返回 1，导致错误

5. 空数组的处理

当 nums.size()==0 时，right = nums.size()-1 = -1，循环条件 left<=right（0<=-1）不成立，直接进入边界检查，返回 -1，符合预期

五、时间复杂度与空间复杂度分析

1. 时间复杂度：`O(log n)`

左边界查找：每次循环将区间缩小一半，最多执行 log2(n) 次（如 n=1e5 时，log2(1e5)≈17）
右边界查找：同理，也是 O(log n)
总时间复杂度：O(log n) + O(log n) = O(log n)，满足题目要求

2. 空间复杂度：`O(1)`

仅使用 left、right、mid 三个临时变量，无额外空间开销（不考虑函数返回值的数组空间）

六、测试用例全覆盖（验证代码正确性）

1. 常规场景

输入：nums=[5,7,7,8,8,10], target=8 → 输出 [3,4]（正确）

2. 目标不存在

输入：nums=[5,7,7,8,8,10], target=6 → 输出 [-1,-1]（正确）

3. 空数组

输入：nums=[], target=0 → 输出 [-1,-1]（正确）

4. 目标是唯一元素

输入：nums=[6], target=6 → 输出 [0,0]（正确）

5. 数组全是目标元素

输入：nums=[2,2,2], target=2 → 输出 [0,2]（正确）

6. 目标在数组开头

输入：nums=[2,2,3,4], target=2 → 输出 [0,1]（正确）

7. 目标在数组结尾

输入：nums=[1,3,5,5], target=5 → 输出 [2,3]（正确）

8. 目标小于所有元素

输入：nums=[2,4,6], target=1 → 输出 [-1,-1]（正确）

9. 目标大于所有元素

输入：nums=[2,4,6], target=7 → 输出 [-1,-1]（正确）

七、总结

本题的核心是「二分搜索找边界」，关键在于理解「找到目标后不返回，继续收缩范围」的逻辑：

左边界：找到目标后收缩右边界（right=mid-1），向左逼近
右边界：找到目标后收缩左边界（left=mid+1），向右逼近
边界检查：循环终止后需验证结果的有效性，避免误判

你提供的代码完美契合「左闭右闭」范式，逻辑严谨，只需注意边界检查的完整性，即可通过所有测试用例。这种解法时间复杂度最优，是面试中的标准解法，掌握后可应对所有「二分找边界」类问题。

3 为什么 return 要用花括号包裹

【是因为return 多个值需要花括号吗？】

你的理解方向是对的！

但更准确的说法是：不是 “return 多个值需要花括号”，而是花括号在这里构造了一个「临时 vector 对象」，return 实际只返回了这一个 vector 对象 —— 这个对象里包含了两个元素（左边界、右边界），从而间接实现了 “返回多个结果” 的效果。

要彻底搞懂，我们需要从 C++ 的「返回值规则」和「vector 初始化语法」两方面拆解：

一、先明确：C++ 函数不能直接返回多个独立值

C++ 的函数返回值规则是「单值返回」—— 一个函数只能返回一个数据（可以是 int、string、自定义类对象等），不能直接写 return a, b;（这是逗号表达式，实际只返回最后一个值 b）。

比如本题需要返回「左边界 + 右边界」两个整数，直接 return left, right; 是错误的，编译器只会返回 right，丢弃 left。

那怎么实现 “返回多个结果”？核心思路是：把多个值 “打包” 成一个「单一对象」，返回这个对象即可。本题中用的「vector<int>」就是这个 “打包容器”——vector 是 C++ 的动态数组，可以存储多个同类型元素，正好能装下两个边界值。

二、花括号 `{}` 的作用：构造临时 vector 对象

return {left, right}; 等价于 return vector<int>{left, right};，花括号在这里是「列表初始化（uniform initialization）」语法，作用是：

在 return 语句中直接构造一个临时的 vector<int>对象，这个对象包含两个元素：left（第一个元素）、right（第二个元素），然后函数返回这个临时对象。

举个直观的对比：

// 写法1：显式构造vector对象（容易理解）
vector searchRange(...) {int left = ...;int right = ...;vector result = {left, right}; // 用花括号初始化vectorreturn result; // 返回这个vector对象
}
// 写法2：隐式构造临时vector对象（你的代码写法）
vector searchRange(...) {int left = ...;int right = ...;return {left, right}; // 直接用花括号构造临时vector，省略显式声明
}

这两种写法完全等价，编译器会自动将 {left, right} 解析为「包含 left 和 right 的 vector<int>临时对象」，然后返回给函数调用者。

三、为什么能这样写？依赖两个 C++ 特性

vector 支持列表初始化：C++11 及以后，vector 允许用花括号 {} 直接初始化元素，比如 vector<int> arr = {1,2,3}; 是合法的，会创建一个包含 1、2、3 的 vector。
函数返回值的隐式类型转换：函数返回类型是 vector<int>，而 {left, right} 能被编译器自动转换为 vector<int> 类型，因此可以直接写在 return 后，无需显式声明。

四、常见误区澄清

误区：“花括号是用来包裹多个返回值的”纠正：花括号是用来「初始化 vector 对象」的，返回的依然是一个单一的 vector 对象，不是多个独立值。
误区：“只有 vector 能用这种写法”纠正：所有支持列表初始化的类型都可以，比如返回 pair<int, int>（另一种打包两个值的类型）：
```
pair searchRange(...) {int left = ...;int right = ...;return {left, right}; // 构造临时pair对象，同样合法
}
```
本题要求返回「数组」（LeetCode 中 vector 和数组在输出时等价），因此用 vector 更合适。

五、总结

return {left, right}; 的本质的是：

利用 C++ 的列表初始化语法，快速构造一个包含两个边界值的 vector<int> 临时对象；
函数返回这个单一的 vector 对象，间接实现 “返回多个结果” 的需求；
这种写法简洁高效，是 C++ 中处理 “多结果返回” 的常用技巧（尤其在 LeetCode 等算法题中）。

简单记：当函数需要返回多个同类型值时，用 vector 打包，花括号直接初始化后返回，本质是返回一个包含所有结果的 vector 对象。

万宁市网站建设_网站建设公司_移动端适配_seo优化