文章目录
- C++ 二分查找详解：基础题解与思维分析
- 前言
- 第一章：热身练习
- 1.1 二分查找基本实现
- 解题思路
- 图解分析
- C++代码实现
- 易错点提示
- 代码解读
- 1.2 在排序数组中查找元素的第一个和最后一个位置
- 解题思路
- 1.2.1 查找左边界
- 算法步骤：
- 图解分析
- C++代码实现
- 1.2.2 查找右边界
- 算法步骤：
- 图解分析
- C++代码实现
- 1.2.3 组合查找结果
- C++完整代码
- 1.3 搜索插入位置
- 解题思路
- 1.3.1 二分查找算法分析
- 算法步骤：
- 图解分析
- C++代码实现
- 易错点提示
- 代码解读
- 1.4 x 的平方根
- 解题思路
- 1.4.1 暴力查找
- 算法步骤：
- C++代码实现
- 图解分析
- 1.4.2 二分查找法
- 算法步骤：
- 图解分析
- C++代码实现
- 易错点提示
- 代码解读
- 写在最后
- 二分查找算法总结
- 重要的三点：
- 模板记忆技巧
- 两段式的特殊处理：
C++ 二分查找详解：基础题解与思维分析
💬 欢迎讨论：如有疑问或见解，欢迎在评论区留言互动。
👍 点赞、收藏与分享：如觉得这篇文章对您有帮助，请点赞、收藏并分享！
🚀 分享给更多人：欢迎分享给更多对 C++ 感兴趣的朋友，一起学习二分查找的基础与进阶！
前言
二分查找法是经典的搜索算法之一，能够在有序数组中快速查找目标元素。它的时间复杂度为
O(log n)，相比于线性搜索有着更高的效率。本篇博客将详细分析二分查找的原理，并结合题目讲解，帮助大家全面掌握这一重要的算法技巧。
第一章：热身练习
1.1 二分查找基本实现
题目链接：704. 二分查找
题目描述：
给定一个升序排列的整数数组 nums，和一个目标值 target。如果 target 在数组中存在，返回其下标；否则，返回 -1。
示例 1：
- 输入：
nums = [-1,0,3,5,9,12],target = 9 - 输出：
4 - 解释：
9出现在nums中，并且下标为4。
示例 2：
- 输入：
nums = [-1,0,3,5,9,12],target = 2 - 输出：
-1 - 解释：
2不存在nums中，因此返回-1。
提示：
- 你可以假设数组中的所有元素是互不相同的。
- 数组
nums的长度范围为[1, 10000]。 - 数组
nums的每个元素都在[-9999, 9999]之间。
解题思路
二分查找的核心思想是利用数组的有序性，通过每次将查找范围缩小一半来快速锁定目标位置。我们在数组的中间位置进行比较，根据比较结果判断应该继续在左侧还是右侧进行查找。
具体思路如下：
-
初始化左右指针：
left指向数组的起始位置。right指向数组的末尾位置。
-
计算中间位置：
- 通过公式
mid = left + (right - left) / 2来计算中间位置mid。这个公式可以避免直接相加left + right可能导致的整数溢出。
- 通过公式
-
比较中间元素与目标值：
- 如果
nums[mid] == target，则直接返回mid。 - 如果
nums[mid] > target，说明目标值在左半部分，此时应将right更新为mid - 1。 - 如果
nums[mid] < target，说明目标值在右半部分，此时应将left更新为mid + 1。
- 如果
-
结束条件：
- 当
left > right时，说明查找范围为空，目标值不存在，返回-1。
- 当
图解分析
假设数组 nums = [-1, 0, 3, 5, 9, 12]，目标值 target = 9。我们从数组的中间位置开始查找：
-
初始状态：
left = 0，right = 5。- 中间位置
mid = (0 + 5) / 2 = 2，nums[mid] = 3。 - 因为
3 < 9，所以更新left = mid + 1 = 3。
-
步骤 1：
left = 3，right = 5。- 中间位置
mid = (3 + 5) / 2 = 4，nums[mid] = 9。 - 找到目标值
9，返回下标4。
步骤图解：
| Iteration | left Pointer | right Pointer | mid Pointer | Array State |
|---|---|---|---|---|
| 1 | 0 | 5 | 2 | [-1, 0, 3, 5, 9, 12] |
| 2 | 3 | 5 | 4 | [5, 9, 12] |
C++代码实现
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
// 计算中间位置，防止溢出
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid; // 找到目标，返回下标
} else if (nums[mid] > target) {
right = mid - 1; // 缩小查找范围至左半部分
} else {
left = mid + 1; // 缩小查找范围至右半部分
}
}
return -1; // 未找到目标，返回 -1
}
};
易错点提示
- 防止溢出：计算中间位置时，建议使用
mid = left + (right - left) / 2，而不是mid = (left + right) / 2，这样可以避免left + right直接相加时可能的整数溢出问题。 - 循环条件：
while (left <= right)，当left和right指向相同元素时，仍然需要继续判断，因此需要取等号。 - 边界条件处理：如果目标值不存在于数组中，应返回
-1，避免返回无效的数组下标。
代码解读
- 时间复杂度：每次查找都会将查找范围缩小一半，因此时间复杂度为
O(log n)。 - 空间复杂度：该算法仅使用了少量额外的变量，空间复杂度为
O(1)。
1.2 在排序数组中查找元素的第一个和最后一个位置
题目链接：34. 在排序数组中查找元素的第一个和最后一个位置
题目描述：
给定一个按非递减顺序排列的整数数组 nums，和一个目标值 target，请找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
示例 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不存在于数组中，因此返回[-1, -1]。
示例 3：
- 输入：
nums = [],target = 0 - 输出：
[-1, -1] - 解释：空数组中没有任何目标值，因此返回
[-1, -1]。
提示：
0 <= nums.length <= 105。-109 <= nums[i] <= 109。nums是一个非递减数组。-109 <= target <= 109。
解题思路
我们需要在时间复杂度
O(log n)内找到目标值的起始位置和结束位置，这意味着必须使用二分查找来解决问题。
基本思路：通过两次二分查找，分别找到目标值的左边界和右边界。
- 左边界：找到数组中第一个等于目标值的位置。
- 右边界：找到数组中最后一个等于目标值的位置。
接下来分别介绍如何查找这两个边界。
1.2.1 查找左边界
我们首先使用二分查找来确定目标值的起始位置，即左边界。
算法步骤：
-
初始化左右指针：
left指向数组的起始位置，right指向数组的末尾位置。
-
进行二分查找：
- 计算中间位置
mid = left + (right - left) / 2。 - 如果
nums[mid]小于目标值target，则说明目标值在右边，因此更新left = mid + 1。 - 如果
nums[mid]大于或等于目标值，说明目标值在左边（包括mid位置），因此更新right = mid。
- 计算中间位置
-
结束条件：当
left == right时，查找结束。此时需要检查nums[left]是否等于目标值，如果相等，返回该位置；否则返回-1。
图解分析
假设数组为 nums = [5,7,7,8,8,10]，目标值为 target = 8。我们从数组的中间位置开始查找：
-
初始状态：
left = 0,right = 5。- 计算中间位置
mid = (0 + 5) / 2 = 2，此时nums[mid] = 7。 - 因为
7 < 8，所以更新left = mid + 1 = 3。
-
步骤 1：
left = 3,right = 5。- 计算中间位置
mid = (3 + 5) / 2 = 4，此时nums[mid] = 8。 - 因为
nums[mid] >= 8，所以更新right = mid = 4。
-
步骤 2：
left = 3,right = 4。- 计算中间位置
mid = (3 + 4) / 2 = 3，此时nums[mid] = 8。 - 因为
nums[mid] >= 8，所以更新right = mid = 3。
-
结束状态：
- 此时
left == right == 3，我们检查nums[left] == 8，因此找到了目标值的起始位置3。
- 此时
C++代码实现
class Solution {
public:
int searchLeft(vector<int>& 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 {
right = mid; // 保持目标值在左半部分
}
}
if (nums.size() == 0 || nums[left] != target) return -1; // 边界条件检查
return left;
}
};
1.2.2 查找右边界
接下来，我们使用二分查找找到目标值的结束位置，即右边界。
算法步骤：
-
初始化左右指针：
left指向数组的起始位置，right指向数组的末尾位置。
-
进行二分查找：
- 计算中间位置
mid = left + (right - left + 1) / 2（向上取整）。 - 如果
nums[mid]小于等于目标值target，则更新left = mid。 - 如果
nums[mid]大于目标值，说明目标值在左边，因此更新right = mid - 1。
- 计算中间位置
-
结束条件：当
left == right时，查找结束，此时left指向目标值的结束位置。
图解分析
假设数组为 nums = [5,7,7,8,8,10]，目标值为 target = 8。我们从中间位置开始查找结束位置：
-
初始状态：
left = 0,right = 5。- 计算
mid = (0 + 5 + 1) / 2 = 3，此时nums[mid] = 8。 - 因为
nums[mid] <= 8，所以更新left = mid = 3。
-
步骤 1：
left = 3,right = 5。- 计算
mid = (3 + 5 + 1) / 2 = 4，此时nums[mid] = 8。 - 因为
nums[mid] <= 8，所以更新left = mid = 4。
-
步骤 2：
left = 4,right = 5。- 计算
mid = (4 + 5 + 1) / 2 = 5，此时nums[mid] = 10。 - 因为
nums[mid] > 8，所以更新right = mid - 1 = 4。
-
结束状态：
- 此时
left == right == 4，因此找到了目标值的结束位置4。
- 此时
C++代码实现
class Solution {
public:
int searchRight(vector<int>& nums, int target) {
int 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;
}
}
return left; // 此时 left 指向最后一个目标值的位置
}
};
1.2.3 组合查找结果
最后，我们将左边界和右边界的查找结果组合起来。如果左边
界的查找结果为 -1，则说明目标值不存在，返回 [-1, -1]。否则，返回 [left, right]。
C++完整代码
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int left = searchLeft(nums, target);
if (left == -1) return {-1, -1}; // 目标值不存在
int right = searchRight(nums, target);
return {left, right}; // 返回目标值的起始和结束位置
}
};
1.3 搜索插入位置
题目链接：35. 搜索插入位置
题目描述：
给定一个排序数组 nums 和一个目标值 target，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你必须设计并实现时间复杂度为 O(log n) 的算法。
示例 1：
- 输入：
nums = [1,3,5,6],target = 5 - 输出：
2
示例 2：
- 输入：
nums = [1,3,5,6],target = 2 - 输出：
1
示例 3：
- 输入：
nums = [1,3,5,6],target = 7 - 输出：
4
提示:
1 <= nums.length <= 104104 <= nums[i] <= 104- nums 为 无重复元素 的 升序 排列数组
104 <= target <= 104
解题思路
该题的要求是以
O(log n)的时间复杂度找到目标值或者其应该插入的位置，因此我们必须使用二分查找。通过二分查找，我们可以在每次查找中将搜索范围缩小一半，进而快速锁定目标值的位置，或者它应插入的准确位置。
1.3.1 二分查找算法分析
在这道题中，我们通过二分查找来确定目标值的位置。如果目标值存在，直接返回其索引；如果不存在，我们可以通过查找过程中的边界情况确定它的插入位置。
算法步骤：
-
初始化左右指针：
left指向数组的起始位置，right指向数组的末尾位置。
-
进行二分查找：
- 计算中间位置
mid = left + (right - left) / 2。 - 如果
nums[mid]小于目标值target，则目标值可能出现在右边部分，因此更新left = mid + 1。 - 如果
nums[mid]大于或等于目标值，说明目标值可能在左边部分，因此更新right = mid。
- 计算中间位置
-
结束条件：当
left == right时，查找结束。此时的left或right所在的位置就是目标值应插入的位置。
图解分析
假设数组为 nums = [1,3,5,6]，目标值 target = 5。我们从数组的中间位置开始查找目标值的位置或插入位置：
-
初始状态：
left = 0，right = 3。- 计算中间位置
mid = (0 + 3) / 2 = 1，此时nums[mid] = 3。 - 因为
3 < 5，更新left = mid + 1 = 2。
-
步骤 1：
left = 2，right = 3。- 计算中间位置
mid = (2 + 3) / 2 = 2，此时nums[mid] = 5。 - 因为
nums[mid] == 5，找到目标值，返回下标2。
-
插入位置场景：
- 如果
target = 2，则当left = 0和right = 1时，nums[mid] = 1，更新left = 1，最后返回1作为插入位置。
- 如果
步骤图解：
| Iteration | left Pointer | right Pointer | mid Pointer | Array State |
|---|---|---|---|---|
| 1 | 0 | 3 | 1 | [1, 3, 5, 6] |
| 2 | 2 | 3 | 2 | [5, 6] |
C++代码实现
class Solution {
public:
int searchInsert(vector<int>& 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 {
right = mid; // 缩小查找范围至左半部分
}
}
// 最终结果在 left 或 right 位置
if (nums[left] < target) return left + 1;
return left;
}
};
易错点提示
- 二分查找的边界条件：要确保循环结束条件是
left == right，这意味着在查找结束后，left或right位置就是插入点。 - 处理插入位置的返回值：当
nums[left]小于target时，表示目标值应插入到left + 1的位置，否则插入到left位置。
代码解读
- 时间复杂度：每次查找都会将查找范围缩小一半，因此时间复杂度为
O(log n)。 - 空间复杂度：该算法仅使用了少量的额外变量，空间复杂度为
O(1)。
1.4 x 的平方根
题目链接：69. x 的平方根
题目描述：
给定一个非负整数 x，计算并返回 x 的算术平方根。由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5。
示例 1：
- 输入：
x = 4 - 输出：
2
示例 2：
- 输入：
x = 8 - 输出：
2 - 解释：
8的算术平方根是2.82842...，由于返回类型是整数，小数部分将被舍去。
提示：
0 <= x <= 2^31 - 1
解题思路
我们可以通过暴力查找和二分查找两种方法来解决该问题。
暴力查找方法简单直接，逐个枚举可能的平方根，直到找到符合条件的数为止。
二分查找方法则更加高效，利用有序性质通过缩小区间的方式快速锁定平方根。
接下来我们分别详细介绍这两种方法。
1.4.1 暴力查找
暴力查找法的核心思想是从 0 开始枚举所有可能的平方根 i，依次判断 i * i 是否等于或超过目标值 x。一旦找到符合条件的 i，就可以直接返回结果。
算法步骤：
- 遍历所有可能的数：从
i = 0开始，逐一检查i * i是否等于x或者超过x。 - 判断条件：
- 如果
i * i == x，说明找到了平方根，直接返回i。 - 如果
i * i > x，说明i已经超出目标值的平方，返回前一个数i - 1作为平方根。
- 如果
C++代码实现
class Solution {
public:
int mySqrt(int x) {
// 由于两个较大的数相乘可能会超过 int 最大范围，因此用 long long
long long i = 0;
for (i = 0; i <= x; i++) {
// 如果两个数相乘正好等于 x，直接返回 i
if (i * i == x) return i;
// 如果第一次出现两个数相乘大于 x，说明结果是前一个数
if (i * i > x) return i - 1;
}
// 处理边界情况
return -1;
}
};
图解分析
假设 x = 8，我们逐个枚举所有可能的平方根：
- 初始状态：
i = 0，i * i = 0，继续下一次循环。
- 步骤 1：
i = 1，i * i = 1，继续下一次循环。
- 步骤 2：
i = 2，i * i = 4，继续下一次循环。
- 步骤 3：
i = 3，i * i = 9，此时9 > 8，返回前一个数2作为平方根。
暴力法的优缺点：
- 优点：实现简单，直观。
- 缺点：对于较大的输入，时间复杂度为
O(x^1/2)，效率较低。
1.4.2 二分查找法
二分查找法是一种更高效的方式，通过利用平方根的有序性，在查找过程中不断缩小区间，快速找到平方根。
算法步骤：
- 初始化左右指针：
left指向1，right指向x。
- 进行二分查找：
- 计算中间位置
mid = left + (right - left + 1) / 2。 - 如果
mid * mid <= x，说明平方根可能在右半部分，更新left = mid。 - 如果
mid * mid > x，说明平方根在左半部分，更新right = mid - 1。
- 计算中间位置
- 结束条件：当
left == right时，查找结束，此时left就是平方根。
图解分析
假设 x = 8，我们通过二分查找来找到平方根：
- 初始状态：
left = 1，right = 8。- 计算
mid = (1 + 8 + 1) / 2 = 5，此时5 * 5 = 25 > 8，更新right = 4。
- 步骤 1：
left = 1，right = 4。- 计算
mid = (1 + 4 + 1) / 2 = 3，此时3 * 3 = 9 > 8，更新right = 2。
- 步骤 2：
left = 1，right = 2。- 计算
mid = (1 + 2 + 1) / 2 = 2，此时2 * 2 = 4 <= 8，更新left = 2。
结束状态：当 left == right == 2，我们找到了平方根 2。
C++代码实现
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) {
left = mid; // 继续向右半部分查找
} else {
right = mid - 1; // 继续向左半部分查找
}
}
return left; // 返回平方根
}
};
易错点提示
- 防止溢出：在计算中间位置
mid时，使用long long类型，以避免mid * mid超出int的范围导致溢出。 - 边界条件：需要正确处理
x = 0或x = 1的情况。
代码解读
- 时间复杂度：每次查找都会将查找范围缩小一半，因此时间复杂度为
O(log n)。 - 空间复杂度：仅使用了常数级的额外空间，空间复杂度为
O(1)。
写在最后
二分查找算法总结
二分查找并不是通过死记模板就能轻松解决所有问题的。其核心在于分析题意，并据此确定搜索区间。理解问题背后的逻辑，明确要搜索的区间，才能灵活编写二分查找的代码。模板只是工具，关键在于理解和应用。
重要的三点：
- 分析题意，确定搜索区间：根据不同的题目，合理分析查找的区间，避免死记硬套模板。
- 理解区间变化：明确什么时候该舍弃左边区间，什么时候舍弃右边区间，并根据题目特点动态调整指针。
- 不要纠结模板形式：不必执着于左闭右开、左闭右闭等模板，最重要的是理解算法背后的区间划分逻辑。
模板记忆技巧
- 三段式与两段式的选择：
- 在面对不同题目时，不要强行套用模板。通过分析问题中的搜索区间变化，合理选择三段式（左右都参与）或两段式（左右边界一边不参与）。
两段式的特殊处理：
在二分查找中，如何处理中间值
mid的计算至关重要，特别是在更新左右指针的情况下，需要正确地选择向上取整或向下取整，否则可能会出现死循环。
-
当
left = mid时：为了避免死循环，应当向上取整。因为此时left不变，如果不向上取整，mid将会一直是left，无法突破当前的循环状态，导致死循环。- 计算公式为：
mid = left + (right - left + 1) / 2。
- 计算公式为：
-
当
right = mid时：应当向下取整。这样可以保证每次right都会减少，逐步缩小搜索区间。- 计算公式为：
mid = left + (right - left) / 2。
- 计算公式为：
以上就是关于【优选算法篇】在分割中追寻秩序：二分查找的智慧轨迹啦的内容啦，各位大佬有什么问题欢迎在评论区指正，您的支持是我创作的最大动力！❤️
