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] 之间。

---

解题思路

二分查找的核心思想是利用数组的有序性，通过每次将查找范围缩小一半来快速锁定目标位置。我们在数组的中间位置进行比较，根据比较结果判断应该继续在左侧还是右侧进行查找。

具体思路如下：

1. 初始化左右指针：

   • left 指向数组的起始位置。
   • right 指向数组的末尾位置。

2. 计算中间位置：

   • 通过公式 mid = left + (right - left) / 2 来计算中间位置 mid。这个公式可以避免直接相加 left + right 可能导致的整数溢出。

3. 比较中间元素与目标值：

   • 如果 nums[mid] == target，则直接返回 mid。
   • 如果 nums[mid] > target，说明目标值在左半部分，此时应将 right 更新为 mid - 1。
   • 如果 nums[mid] < target，说明目标值在右半部分，此时应将 left 更新为 mid + 1。

4. 结束条件：

   • 当 left > right 时，说明查找范围为空，目标值不存在，返回 -1。

---

图解分析

假设数组 nums = [-1, 0, 3, 5, 9, 12]，目标值 target = 9。我们从数组的中间位置开始查找：

1. 初始状态：

   • left = 0，right = 5。
   • 中间位置 mid = (0 + 5) / 2 = 2，nums[mid] = 3。
   • 因为 3 < 9，所以更新 left = mid + 1 = 3。

2. 步骤 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}
};

---

易错点提示

1. 防止溢出：计算中间位置时，建议使用 mid = left + (right - left) / 2，而不是 mid = (left + right) / 2，这样可以避免 left + right 直接相加时可能的整数溢出问题。
2. 循环条件：while (left <= right)，当 left 和 right 指向相同元素时，仍然需要继续判断，因此需要取等号。
3. 边界条件处理：如果目标值不存在于数组中，应返回 -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.2.1 查找左边界

我们首先使用二分查找来确定目标值的起始位置，即左边界。

算法步骤：

1. 初始化左右指针：

   • left 指向数组的起始位置，right 指向数组的末尾位置。

2. 进行二分查找：

   • 计算中间位置 mid = left + (right - left) / 2。
   • 如果 nums[mid] 小于目标值 target，则说明目标值在右边，因此更新 left = mid + 1。
   • 如果 nums[mid] 大于或等于目标值，说明目标值在左边（包括 mid 位置），因此更新 right = mid。

3. 结束条件：当 left == right 时，查找结束。此时需要检查 nums[left] 是否等于目标值，如果相等，返回该位置；否则返回 -1。

---

图解分析

假设数组为 nums = [5,7,7,8,8,10]，目标值为 target = 8。我们从数组的中间位置开始查找：

1. 初始状态：

   • left = 0, right = 5。
   • 计算中间位置 mid = (0 + 5) / 2 = 2，此时 nums[mid] = 7。
   • 因为 7 < 8，所以更新 left = mid + 1 = 3。

2. 步骤 1：

   • left = 3, right = 5。
   • 计算中间位置 mid = (3 + 5) / 2 = 4，此时 nums[mid] = 8。
   • 因为 nums[mid] >= 8，所以更新 right = mid = 4。

3. 步骤 2：

   • left = 3, right = 4。
   • 计算中间位置 mid = (3 + 4) / 2 = 3，此时 nums[mid] = 8。
   • 因为 nums[mid] >= 8，所以更新 right = mid = 3。

4. 结束状态：

   • 此时 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 查找右边界

接下来，我们使用二分查找找到目标值的结束位置，即右边界。

算法步骤：

1. 初始化左右指针：

   • left 指向数组的起始位置，right 指向数组的末尾位置。

2. 进行二分查找：

   • 计算中间位置 mid = left + (right - left + 1) / 2（向上取整）。
   • 如果 nums[mid] 小于等于目标值 target，则更新 left = mid。
   • 如果 nums[mid] 大于目标值，说明目标值在左边，因此更新 right = mid - 1。

3. 结束条件：当 left == right 时，查找结束，此时 left 指向目标值的结束位置。

---

图解分析

假设数组为 nums = [5,7,7,8,8,10]，目标值为 target = 8。我们从中间位置开始查找结束位置：

1. 初始状态：

   • left = 0, right = 5。
   • 计算 mid = (0 + 5 + 1) / 2 = 3，此时 nums[mid] = 8。
   • 因为 nums[mid] <= 8，所以更新 left = mid = 3。

2. 步骤 1：

   • left = 3, right = 5。
   • 计算 mid = (3 + 5 + 1) / 2 = 4，此时 nums[mid] = 8。
   • 因为 nums[mid] <= 8，所以更新 left = mid = 4。

3. 步骤 2：

   • left = 4, right = 5。
   • 计算 mid = (4 + 5 + 1) / 2 = 5，此时 nums[mid] = 10。
   • 因为 nums[mid] > 8，所以更新 right = mid - 1 = 4。

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 <= 104
• 104 <= nums[i] <= 104
• nums 为 无重复元素 的 升序 排列数组
• 104 <= target <= 104

---

解题思路

该题的要求是以 O(log n) 的时间复杂度找到目标值或者其应该插入的位置，因此我们必须使用二分查找。通过二分查找，我们可以在每次查找中将搜索范围缩小一半，进而快速锁定目标值的位置，或者它应插入的准确位置。

---

1.3.1 二分查找算法分析

在这道题中，我们通过二分查找来确定目标值的位置。如果目标值存在，直接返回其索引；如果不存在，我们可以通过查找过程中的边界情况确定它的插入位置。

算法步骤：

1. 初始化左右指针：

   • left 指向数组的起始位置，right 指向数组的末尾位置。

2. 进行二分查找：

   • 计算中间位置 mid = left + (right - left) / 2。
   • 如果 nums[mid] 小于目标值 target，则目标值可能出现在右边部分，因此更新 left = mid + 1。
   • 如果 nums[mid] 大于或等于目标值，说明目标值可能在左边部分，因此更新 right = mid。

3. 结束条件：当 left == right 时，查找结束。此时的 left 或 right 所在的位置就是目标值应插入的位置。

---

图解分析

假设数组为 nums = [1,3,5,6]，目标值 target = 5。我们从数组的中间位置开始查找目标值的位置或插入位置：

1. 初始状态：

   • left = 0，right = 3。
   • 计算中间位置 mid = (0 + 3) / 2 = 1，此时 nums[mid] = 3。
   • 因为 3 < 5，更新 left = mid + 1 = 2。

2. 步骤 1：

   • left = 2，right = 3。
   • 计算中间位置 mid = (2 + 3) / 2 = 2，此时 nums[mid] = 5。
   • 因为 nums[mid] == 5，找到目标值，返回下标 2。

3. 插入位置场景：

   • 如果 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;}
};

---

易错点提示

1. 二分查找的边界条件：要确保循环结束条件是 left == right，这意味着在查找结束后，left 或 right 位置就是插入点。
2. 处理插入位置的返回值：当 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，就可以直接返回结果。

算法步骤：

1. 遍历所有可能的数：从 i = 0 开始，逐一检查 i * i 是否等于 x 或者超过 x。
2. 判断条件：
   • 如果 i * i == x，说明找到了平方根，直接返回 i。
   • 如果 i * i > x，说明 i 已经超出目标值的平方，返回前一个数 i - 1 作为平方根。

C++代码实现

class Solution {
public:int mySqrt(int x) {// 由于两个较大的数相乘可能会超过 int 最大范围，因此用 long longlong long i = 0;for (i = 0; i <= x; i++) {// 如果两个数相乘正好等于 x，直接返回 iif (i * i == x) return i;// 如果第一次出现两个数相乘大于 x，说明结果是前一个数if (i * i > x) return i - 1;}// 处理边界情况return -1;}
};

---

图解分析

假设 x = 8，我们逐个枚举所有可能的平方根：

1. 初始状态：
   • i = 0，i * i = 0，继续下一次循环。
2. 步骤 1：
   • i = 1，i * i = 1，继续下一次循环。
3. 步骤 2：
   • i = 2，i * i = 4，继续下一次循环。
4. 步骤 3：
   • i = 3，i * i = 9，此时 9 > 8，返回前一个数 2 作为平方根。

暴力法的优缺点：

• 优点：实现简单，直观。
• 缺点：对于较大的输入，时间复杂度为 O(x^1/2)，效率较低。

---

1.4.2 二分查找法

二分查找法是一种更高效的方式，通过利用平方根的有序性，在查找过程中不断缩小区间，快速找到平方根。

算法步骤：

1. 初始化左右指针：
   • left 指向 1，right 指向 x。
2. 进行二分查找：
   • 计算中间位置 mid = left + (right - left + 1) / 2。
   • 如果 mid * mid <= x，说明平方根可能在右半部分，更新 left = mid。
   • 如果 mid * mid > x，说明平方根在左半部分，更新 right = mid - 1。
3. 结束条件：当 left == right 时，查找结束，此时 left 就是平方根。

---

图解分析

假设 x = 8，我们通过二分查找来找到平方根：

1. 初始状态：
   • left = 1，right = 8。
   • 计算 mid = (1 + 8 + 1) / 2 = 5，此时 5 * 5 = 25 > 8，更新 right = 4。
2. 步骤 1：
   • left = 1，right = 4。
   • 计算 mid = (1 + 4 + 1) / 2 = 3，此时 3 * 3 = 9 > 8，更新 right = 2。
3. 步骤 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;  // 返回平方根}
};

---

易错点提示

1. 防止溢出：在计算中间位置 mid 时，使用 long long 类型，以避免 mid * mid 超出 int 的范围导致溢出。
2. 边界条件：需要正确处理 x = 0 或 x = 1 的情况。

---

代码解读

• 时间复杂度：每次查找都会将查找范围缩小一半，因此时间复杂度为 O(log n)。
• 空间复杂度：仅使用了常数级的额外空间，空间复杂度为 O(1)。

---

写在最后

二分查找算法总结

二分查找并不是通过死记模板就能轻松解决所有问题的。其核心在于分析题意，并据此确定搜索区间。理解问题背后的逻辑，明确要搜索的区间，才能灵活编写二分查找的代码。模板只是工具，关键在于理解和应用。

重要的三点：

• 分析题意，确定搜索区间：根据不同的题目，合理分析查找的区间，避免死记硬套模板。
• 理解区间变化：明确什么时候该舍弃左边区间，什么时候舍弃右边区间，并根据题目特点动态调整指针。
• 不要纠结模板形式：不必执着于左闭右开、左闭右闭等模板，最重要的是理解算法背后的区间划分逻辑。

---

模板记忆技巧

1. 三段式与两段式的选择：
   • 在面对不同题目时，不要强行套用模板。通过分析问题中的搜索区间变化，合理选择三段式（左右都参与）或两段式（左右边界一边不参与）。

两段式的特殊处理：

在二分查找中，如何处理中间值 mid 的计算至关重要，特别是在更新左右指针的情况下，需要正确地选择向上取整或向下取整，否则可能会出现死循环。

• 当 left = mid 时：为了避免死循环，应当向上取整。因为此时 left 不变，如果不向上取整，mid 将会一直是 left，无法突破当前的循环状态，导致死循环。

  • 计算公式为：mid = left + (right - left + 1) / 2。

• 当 right = mid 时：应当向下取整。这样可以保证每次 right 都会减少，逐步缩小搜索区间。

  • 计算公式为：mid = left + (right - left) / 2。

---

以上就是关于【优选算法篇】在分割中追寻秩序：二分查找的智慧轨迹啦的内容啦，各位大佬有什么问题欢迎在评论区指正，您的支持是我创作的最大动力！❤️