【优选算法篇】寻找隐藏的宝藏：用二分查找打开算法世界的大门（上篇）

文章目录

须知

💬 欢迎讨论：如果你在学习过程中有任何问题或想法，欢迎在评论区留言，我们一起交流学习。你的支持是我继续创作的动力！

👍 点赞、收藏与分享：觉得这篇文章对你有帮助吗？别忘了点赞、收藏并分享给更多的小伙伴哦！你们的支持是我不断进步的动力！
🚀 分享给更多人：如果你觉得这篇文章对你有帮助，欢迎分享给更多对C++算法感兴趣的朋友，让我们一起进步！

1. C++ 二分查找算法详解

1.1 二分查找算法的重要性

二分查找（Binary Search）是一种经典的算法，广泛应用于计算机科学中，尤其在处理有序数据时。其重要性体现在以下几个方面：

高效性：
- 时间复杂度为 O(log⁡n)，相比于线性搜索的 O(n)，在大规模数据集上，性能提升显著。
- 特别适用于查找频繁的场景，如搜索引擎、数据库索引等。
普适性：
- 不仅可以应用于查找问题，还能扩展到解决复杂问题，如求解特定函数值、二分答案法、优化问题的解空间收缩等。
简洁性：
- 算法简单易实现，逻辑清晰，适合初学者掌握编程和算法的基本思想。
- 二分查找思想可以扩展到多种变体（如上下界查找、最优解逼近等）。
应用广泛：
- 排序数组中的查找问题。
- 数学问题求解（如平方根、最大值最小化等）。
- 各种问题优化（如动态规划中的状态转移点查找）。

1.2 什么是二分查找算法？

二分查找是一种在 有序数组 中查找目标值的算法。通过每次将查找范围缩小一半，逐步逼近目标值的位置。

定义核心：

二分查找的目标是利用有序性，将搜索范围逐步减少到最小。
通过比较中间值与目标值，决定在左右半区继续搜索。

1.3 核心思想

核心思想可以概括为“分而治之”：

缩小搜索范围：
- 每次比较目标值和中间值，根据有序性决定继续查找左半部分还是右半部分，排除另一半不可能的区域。
递归或迭代：
- 通过递归或迭代实现搜索范围不断缩小。
- 最终在可能的区间中找到目标值（或者确认目标值不存在）。
有序性约束：
- 二分查找仅适用于有序数组（或可以逻辑上排序的空间），是其适用性的前提。

二分查找的基本步骤

初始化范围：
- 定义左右边界 left 和 right，初始为数组的起点和终点。
计算中点：
- 根据公式 mid = left + (right - left) / 2 计算中间索引，避免溢出。
判断目标值：
- 如果目标值等于中点值，直接返回。
- 如果目标值小于中点值，缩小右边界 right = mid - 1。
- 如果目标值大于中点值，缩小左边界 left = mid + 1。
退出条件：
- 当 left > right 时，说明目标值不存在，结束搜索。

1.4 二分查找的典型应用

数组查找：
- 在排序数组中快速查找目标值。
上/下界查找：
- 查找目标值的第一个或最后一个出现位置。
函数值逼近：
- 在某范围内寻找特定条件满足的最优值。
复杂问题解空间缩减：
- 如动态规划中的优化问题（状态转移优化）。

2. 二分查找算法模版

2.1 标准二分查找模板

用于在有序数组中查找某个目标值。

int binarySearch(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1;while (left <= right) { // 搜索区间为 [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 时，说明目标值不存在。
时间复杂度：O(log⁡n)。

2.2 查找左侧边界的二分查找

查找目标值的最左位置。

int lowerBound(vector<int>& nums, int target) {int left = 0, right = nums.size();while (left < right) { // 搜索区间为 [left, right)int mid = left + (right - left) / 2;if (nums[mid] < target) {left = mid + 1; // 缩小到右半部分} else {right = mid; // 缩小到左半部分}}return left; // 返回左边界
}

如果目标值存在，返回其左边界索引。
如果目标值不存在，返回插入位置。
适用场景：查找目标值的第一个出现位置，或者获取目标值插入有序数组的位置。

2.3 查找右侧边界的二分查找

查找目标值的最右位置。

int upperBound(vector<int>& nums, int target) {int left = 0, right = nums.size();while (left < right) { // 搜索区间为 [left, right)int mid = left + (right - left) / 2;if (nums[mid] <= target) {left = mid + 1; // 缩小到右半部分} else {right = mid; // 缩小到左半部分}}return left - 1; // 返回右边界索引
}

特点：

如果目标值存在，返回其右边界索引。
如果目标值不存在，返回小于目标值的最大元素位置。

2.4 查找目标值范围（二分查找综合模板）

同时查找目标值的左、右边界（适用于数组中目标值重复出现）。

vector<int> searchRange(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1;// 查找左边界int start = -1, end = -1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] >= target) {right = mid - 1;} else {left = mid + 1;}}if (left < nums.size() && nums[left] == target) {start = left;} else {return {-1, -1}; // 目标值不存在}// 查找右边界left = 0, right = nums.size() - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] <= target) {left = mid + 1;} else {right = mid - 1;}}end = right;return {start, end};
}

特点：

适用于查找区间 [start, end]。
如果目标值不存在，返回 {-1, -1}。

2.5 二分答案法模板

适用于需要在范围内找到满足某种条件的最优解。

int binaryAnswer(int low, int high, function<bool(int)> condition) {while (low < high) {int mid = low + (high - low) / 2;if (condition(mid)) {high = mid; // 满足条件，收缩右边界} else {low = mid + 1; // 不满足条件，收缩左边界}}return low; // 返回最小满足条件的值
}

特点：

通过逻辑条件函数 condition(mid) 判断是否满足目标。
常用于优化问题，如最大值最小化、最小值最大化等。

2.6 常见边界问题注意点

搜索区间是否包含 right：
- [left, right] 区间通常用于包含上下界查找。
- [left, right) 区间通常用于统一逻辑，更适合下界查找。
mid 计算防止溢出：
- 使用 mid = left + (right - left) / 2。
退出条件的灵活性：
- 对于不同区间范围和边界需求，while (left <= right) 和 while (left < right) 需区别对待。

2.7 总结

标准模板：快速定位目标值。
变体模板：查找上下界或目标值范围。
扩展模板：适用于更复杂的优化问题。掌握不同场景下的二分查找模板，能够快速高效解决查找与优化问题。

3. 题目1：二分查找

题目链接：704. 二分查找 - 力扣（LeetCode）

题目描述：

3.1 算法思路：

核心思想

利用 二分查找算法，在有序数组中查找目标值。每次通过比较中间值与目标值的大小，缩小搜索范围，直到找到目标值或搜索范围为空。

3.1.1 具体步骤

初始化搜索范围：
- 左边界 left 初始化为数组起点 0。
- 右边界 right 初始化为数组终点 nums.size() - 1。
二分循环查找：
- 当 left <= right 时：
  - 计算中间索引 mid = left + (right - left) / 2（避免整数溢出）。
  - 如果 nums[mid] == target，直接返回索引 mid。
  - 如果 nums[mid] < target，目标值在右半部分，将 left 更新为 mid + 1。
  - 如果 nums[mid] > target，目标值在左半部分，将 right 更新为 mid - 1。
返回结果：
- 如果退出循环仍未找到目标值，返回 -1。

3.2 示例代码：

class Solution {
public:int search(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1;while (left <= right) { // 搜索区间为 [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; // 未找到目标值}
};

3.2.1 示例解析

示例 1：

输入：nums = [-1, 0, 3, 5, 9, 12], target = 9 输出：4

执行过程：

初始化：left = 0, right = 5。
第 1 步：mid = (0 + 5) / 2 = 2，nums[mid] = 3 < 9，更新 left = 3。
第 2 步：mid = (3 + 5) / 2 = 4，nums[mid] = 9 == 9，返回索引 4。

3.3 时间与空间复杂度

3.3.1 时间复杂度：

O(log n)：
- 每次迭代将搜索范围缩小一半，因此时间复杂度是对数级别。

3.3.2 空间复杂度：

O(1)：
- 只使用了常数空间，无额外数组或递归调用栈。

边界条件分析

空数组：
- 如果 nums 为空，right = nums.size() - 1 = -1，循环直接跳过，返回 -1。
目标值不在数组中：
- 如果目标值不在数组中，循环最终会将 left > right，返回 -1。
目标值在边界：
- 如果目标值是数组中的最小值或最大值，算法可以正确返回索引。

3.4 补充（可看可不看）

暴力解法

3.4.1 暴力解法思路

暴力解法的核心是直接遍历数组 nums 中的每一个元素，逐一与目标值 target 进行比较，直到找到目标值或遍历结束。

3.4.2 具体步骤

遍历数组：
- 从左到右逐一访问数组中的每一个元素。
比较当前元素与目标值：
- 如果当前元素等于目标值，返回当前索引。
返回结果：
- 如果遍历结束仍未找到目标值，返回 -1 表示目标值不存在。

3.4.3 示例代码：

class Solution {
public:int search(vector<int>& nums, int target) {for (int i = 0; i < nums.size(); i++) {if (nums[i] == target) {return i; // 找到目标值，返回索引}}return -1; // 未找到目标值}
};

3.4.4 时间与空间复杂度

时间复杂度：

最坏情况：
- 当目标值位于数组末尾或者不存在时，需要遍历整个数组，时间复杂度为 O(n)，其中 n 是数组长度。
最佳情况：
- 当目标值是数组中的第一个元素时，时间复杂度为 O(1)。
平均情况：
- O(n)，因为没有利用数组的有序性。

空间复杂度：

O(1)：
- 只使用了常量级别的额外空间，没有引入新的数据结构。

暴力解法的优缺点

优点：

简单直接：
- 实现简单，逻辑清晰。
- 对初学者友好，无需理解复杂算法。
通用性强：
- 无需假设数组是有序的，可直接用于任意数组。

缺点：

效率低下：
- 对于大规模数组，时间复杂度 O(n) 远高于二分查找的 O(log⁡n)。
- 未利用数组的有序性，性能不佳。
不符合题目要求：
- 题目中数组是有序的，暴力解法没有利用这一特性。

3.4.5 与二分查找对比

3.4.6 总结：

暴力解法逻辑简单，适合入门或小规模数据场景。
二分查找则充分利用了有序数组的特性，更适合大规模查找，性能更优。

3.5 总结：

算法思路：利用有序数组的性质，每次缩小搜索范围，逐步找到目标值或确定其不存在。
时间复杂度：O(log⁡n)，适合大规模数据的查找。
边界处理：代码能够正确处理空数组、目标值不在数组中、目标值在边界等特殊情况。

4. 题目2：在排序数组中查找元素的第一个和最后一个位置

题目链接：34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

题目描述：

4.1 算法思路：

这道题的核心是利用 二分查找 在排序数组中分别找到目标值的左右边界。

1. 核心思想

找到左边界（第一个等于 target 的元素的索引）。
找到右边界（最后一个等于 target 的元素的索引）。
如果找不到目标值，直接返回 [-1, -1]。

2. 使用两次二分查找

查找左边界：定位目标值在数组中的最左位置。
查找右边界：定位目标值在数组中的最右位置。

4.2 示例代码：

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {// 查找左边界int left = 0, right = nums.size() - 1;int leftIndex = -1, rightIndex = -1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] >= target) {right = mid - 1;} else {left = mid + 1;}}if (left < nums.size() && nums[left] == target) {leftIndex = left;} else {return {-1, -1}; // 如果左边界不存在，直接返回}// 查找右边界left = 0, right = nums.size() - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] <= target) {left = mid + 1;} else {right = mid - 1;}}if (right >= 0 && nums[right] == target) {rightIndex = right;}return {leftIndex, rightIndex};}
};

详细步骤

4.2.1 查找左边界

初始化 left = 0，right = nums.size() - 1。
在循环中，通过二分查找找到第一个大于或等于 target 的位置：
- 如果 nums[mid] < target，则目标值在右侧，调整 left = mid + 1。
- 如果 nums[mid] >= target，则调整 right = mid - 1。
最后检查 nums[left] 是否等于 target，如果相等，返回 left，否则返回 -1。

4.2.2 查找右边界

初始化 left = 0，right = nums.size() - 1。
在循环中，通过二分查找找到最后一个小于或等于 target 的位置：
- 如果 nums[mid] > target，则目标值在左侧，调整 right = mid - 1。
- 如果 nums[mid] <= target，则调整 left = mid + 1。
最后检查 nums[right] 是否等于 target，如果相等，返回 right，否则返回 -1。

示例解析

示例 1：

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

执行过程：

查找左边界：
- 初始范围：left = 0, right = 5。
- 第一次：mid = 2，nums[2] = 7 < 8，更新 left = 3。
- 第二次：mid = 4，nums[4] = 8，更新 right = 3。
- 第三次：mid = 3，nums[3] = 8，更新 right = 2。
- 左边界为 3。
查找右边界：
- 初始范围：left = 0, right = 5。
- 第一次：mid = 2，nums[2] = 7 < 8，更新 left = 3。
- 第二次：mid = 4，nums[4] = 8，更新 left = 5。
- 第三次：mid = 5，nums[5] = 10 > 8，更新 right = 4。
- 右边界为 4。

输出：

[3,4]

4.3 时间与空间复杂度

4.3.1 时间复杂度

每次二分查找的时间复杂度为 O(log⁡n)。
两次二分查找，总时间复杂度为 O(2⋅logn)=O(logn)。

4.3.2 空间复杂度

只使用常量级额外空间，空间复杂度为 O(1)。

4.4 总结：

算法特点：
- 使用二分查找分别找到左边界和右边界。
- 时间复杂度 O(log⁡n)，适合大规模数据。
- 空间复杂度 O(1)，仅使用常量级变量。
代码结构清晰：
- 两次独立的二分查找，易于理解和调试。
特殊情况处理：
- 数组为空或目标值不存在时，返回 [-1, -1]。

5. 题目3：搜索插入位置

题目链接：35. 搜索插入位置 - 力扣（LeetCode）

题目描述：

5.1 算法思路：

核心思想：二分查找

由于数组是升序排序的，因此可以使用二分查找在 O(log⁡n) 时间复杂度内找到目标值的插入位置。

5.2 示例代码：

class Solution
{
public:int searchInsert(vector<int>& nums, int target) {// 定义左右边界int left = 0, right = nums.size() - 1;// 特殊情况：如果目标值大于数组中所有元素，则插入到数组末尾if (nums[right] < target)  return right + 1;// 二分查找while (left < right) {// 计算中间位置，避免溢出int mid = left + (right - left) / 2;// 如果中间值小于目标值，目标值在右半部分if (nums[mid] < target)  left = mid + 1; // 调整左边界else // 如果中间值大于等于目标值，目标值可能在左半部分right = mid;     // 调整右边界}// 最终 left == right，返回插入位置return left;}
};

5.2.1 注释内容说明

特殊处理（nums[right] < target）：
- 如果目标值大于数组中的最大值，则目标值一定插入到数组末尾。
- 为了提高效率，先检查这一特殊情况。
二分查找核心：
- 使用 while (left < right) 循环，通过不断缩小区间找到目标值或插入位置。
- 使用 mid = left + (right - left) / 2 计算中点，避免 left + right 的溢出问题。
区间调整逻辑：
- 当 nums[mid] < target 时，说明目标值在右半部分，更新左边界 left = mid + 1。
- 否则，目标值在左半部分或 nums[mid] == target，更新右边界 right = mid。
最终返回：
- 循环退出时，left == right，此时 left 即为目标值所在位置或插入位置。

5.3 时间与空间复杂度

时间复杂度：O(log⁡n)
- 二分查找每次将搜索范围缩小一半，复杂度是对数级。
空间复杂度：O(1)
- 无额外空间开销。

5.4 补充（可看可不看）

5.4.1 暴力解法

暴力解法的核心是 直接遍历数组：

遍历数组中的每个元素，与目标值 target 进行比较。
如果找到一个元素大于或等于目标值，返回该元素的索引。
如果遍历结束仍未找到，说明目标值比数组中所有元素都大，返回数组的长度。

这种方法时间复杂度是 O(n)，适合小规模数组。

5.4.2 示例代码：

class Solution
{
public:int searchInsert(vector<int>& nums, int target) {for (int i = 0; i < nums.size(); i++) {// 如果找到第一个大于或等于目标值的位置，返回索引if (nums[i] >= target) return i;}// 如果目标值比所有元素都大，返回数组长度return nums.size();}
};

5.4.3 示例解析

示例 1：

输入：nums = [1, 3, 5, 6], target = 5 输出：2

执行过程：

遍历到 nums[0] = 1，1 < 5，继续。
遍历到 nums[1] = 3，3 < 5，继续。
遍历到 nums[2] = 5，5 >= 5，返回索引 2。

5.4.4 时间与空间复杂度

时间复杂度：

最坏情况：目标值比数组所有元素都大，需要遍历整个数组，时间复杂度为 O(n)。
最佳情况：目标值小于数组第一个元素，直接返回索引 0，时间复杂度为 O(1)。

空间复杂度：

O(1)：不需要额外的存储空间。

优缺点分析

优点：

简单直接，易于实现。
适合小规模数组的情况。

缺点：

时间复杂度较高，不适合大规模数组。
没有利用数组的有序性，效率较低。

5.5 总结：

关键点：
- 明确目标值可能是数组中的一个元素，也可能是插入的位置。
- 使用二分查找，高效缩小范围。
- 返回 left 即为插入位置。
扩展场景：
- 如果需要返回目标值的插入位置，同时要求区分左、右边界，可以进一步扩展这段代码逻辑。

6. 题目4：x的平方根

题目链接：69. x 的平方根 - 力扣（LeetCode）

题目描述：

6.1 算法思路：

6.1.1 问题本质

我们要找到满足以下条件的最大整数 y：

y2≤x
(y+1)2>x

6.1.2 核心思想

利用 二分查找 来寻找平方根：

二分查找的搜索区间是 [1, x]（因为 x\sqrt{x}x 最大不会超过 x 本身）。
每次取中点 mid，计算 mid2 与 x 比较：
- 如果 mid2 ≤ x，说明平方根在右侧，更新 left = mid。
- 如果 mid2 > x，说明平方根在左侧，更新 right = mid - 1。
循环退出时，left 指向平方根的整数部分。

6.2 示例代码：

class Solution 
{
public:int mySqrt(int x) {if (x < 1) return 0;  // 特殊情况处理int left = 1, right = x;  // 定义二分查找的边界while (left < right) {long long mid = left + (right - left + 1) / 2;  // 向上取整计算中点if (mid * mid > x) right = mid - 1;  // 排除右半部分else left = mid;  // 更新左边界，保留 mid}return left;  // 最终返回平方根的整数部分}
};

版本2：

class Solution 
{
public:int mySqrt(int x) {if (x == 0) return 0;  // 直接处理特殊情况int left = 1, right = x;while (left <= right)  // 使用闭区间 [left, right]{int mid = left + (right - left) / 2;if (mid <= x / mid)  // 避免溢出left = mid + 1;  // 更新左边界elseright = mid - 1; // 更新右边界}return right;  // 返回右边界，即平方根整数部分}
};

6.2.1 关键点解析

初始化区间：
- 区间为 [1, x]，因为平方根不会小于 1 且不会大于 x（对于 x≥1）。
中点计算：
- 使用 mid = left + (right - left + 1) / 2 来计算中点，避免直接加法可能导致的溢出。
- 向上取整 的目的是保证当区间只有两个元素时，选择靠右的中点，从而能够正确排除区间。
更新区间：
- 如果 mid2>x：right = mid - 1，排除当前的 mid 和右侧部分。
- 如果 mid2<=x：left = mid，保留当前的 mid。
返回值：
- 循环退出条件是 left == right，此时 left 即为平方根的整数部分。

6.3 补充（可看可不看）

暴力解法

6.3.1 示例代码：

class Solution 
{
public:int mySqrt(int x) {if (x == 0) return 0;  // 特殊情况处理int y = 0;while ((long long)y * y <= x)  // 防止溢出{y++;}return y - 1;  // 返回满足条件的最大整数}
};

6.3.2 时间与空间复杂度

时间复杂度

最坏情况：如果 x 很大（如 x = 10^9），暴力解法需要从 0 遍历到 x\sqrt{x}，因此时间复杂度为 O(x\sqrt{x})。
最佳情况：如果 x=0 或 x=1，复杂度为 O(1)。

空间复杂度

O(1)：仅使用了常量级别的变量 y 和计算，不需要额外空间。

优缺点分析

优点

简单直观：
- 不依赖复杂的算法逻辑，直接枚举。
- 易于理解和实现。
无特殊处理：
- 不需要处理二分查找的边界条件，也无需考虑浮点数计算误差。

缺点

效率低下：
- 时间复杂度为 O(\sqrt{x})，对于较大的 x（如 10^9），效率明显低于二分查找法的 O(log⁡x)。
对大数的适用性差：
- 如果没有使用 long long 类型，会因为 y2 的溢出问题导致错误结果。

6.4 时间与空间复杂度

6.4.1 时间复杂度

二分查找的时间复杂度是 O(log⁡x)，因为每次迭代将搜索区间缩小一半。

6.4.2 空间复杂度

只使用了常量额外空间，空间复杂度是 O(1)。

6.5 对比

6.6 总结

算法思想：
- 二分查找用于在区间 [1, x] 中寻找满足 y2≤x 的最大整数 y。
复杂度：
- 时间复杂度 O(log⁡x)，空间复杂度 O(1)。
注意事项：
- 需要特别处理 x = 0 和 x = 1 等特殊情况。
- 通过 mid <= x / mid 避免溢出问题。