C++.二分法教程

1. 问题引入

1.1 猜数字游戏

在日常生活中，我们经常会遇到需要快速查找目标值的情况。例如，猜数字游戏就是一个典型的场景。假设你和朋友玩一个游戏，朋友心中想了一个1到100之间的数字，你需要通过最少的猜测次数来猜出这个数字。每次猜测后，朋友会告诉你猜的数字是大了、小了还是正好。这种场景非常适合使用二分法来解决。

二分法的核心思想是通过不断地将查找范围缩小一半，从而快速定位目标值。在猜数字游戏中，你可以先猜50，如果朋友说数字大了，那么目标值一定在51到100之间；如果朋友说数字小了，那么目标值一定在1到49之间。通过这种方式，每次猜测都能将查找范围缩小一半，从而快速找到目标值。

为了更好地理解二分法的逻辑，我们可以用思维导图来梳理整个过程：

猜数字游戏
├── 初始范围：1到100
├── 猜测过程
│   ├── 计算中间值：(low + high) / 2
│   ├── 比较中间值与目标值
│   │   ├── 如果中间值等于目标值：结束
│   │   ├── 如果中间值大于目标值：调整范围为low到mid-1
│   │   └── 如果中间值小于目标值：调整范围为mid+1到high
│   └── 重复猜测过程
└── 结束条件：找到目标值或范围为空

接下来，我们通过一个具体的示例代码来实现这个猜数字游戏，从而更好地理解二分法的实现过程。# 2. 二分法思维导图

2.1 二分法核心思想

二分法是一种高效的查找算法，其核心思想是通过不断地将查找范围缩小一半，从而快速定位目标值。这种方法在有序数据中查找目标值时特别有效。以下是二分法核心思想的详细分析：

为什么需要二分法？

在实际应用中，我们经常需要在大量数据中查找某个特定值。如果使用线性查找（逐个比较），时间复杂度为O(n)，当数据量较大时，查找效率会非常低。而二分法通过每次将查找范围缩小一半，时间复杂度仅为O(log n)，大大提高了查找效率。

二分法的基本步骤

1. 确定查找范围：假设有一个有序数组，查找范围的初始值为数组的起始位置low和结束位置high。
2. 计算中间值：通过(low + high) / 2计算中间位置mid，并获取中间值。
3. 比较中间值与目标值：
   • 如果中间值等于目标值，查找成功，返回中间位置mid。
   • 如果中间值大于目标值，说明目标值在左半部分，调整查找范围为low到mid - 1。
   • 如果中间值小于目标值，说明目标值在右半部分，调整查找范围为mid + 1到high。
4. 重复步骤2和3：直到找到目标值或查找范围为空（low > high）。

示例代码

以下是一个简单的二分查找函数实现，用于在有序数组中查找目标值：

#include <iostream>
using namespace std;// 二分查找函数
int binarySearch(int arr[], int low, int high, int target) {while (low <= high) {int mid = low + (high - low) / 2; // 防止溢出if (arr[mid] == target) {return mid; // 找到目标值，返回索引} else if (arr[mid] < target) {low = mid + 1; // 调整查找范围到右半部分} else {high = mid - 1; // 调整查找范围到左半部分}}return -1; // 未找到目标值，返回-1
}int main() {int arr[] = {1, 3, 5, 7, 9, 11, 13, 15}; // 有序数组int target = 7; // 目标值int result = binarySearch(arr, 0, sizeof(arr) / sizeof(arr[0]) - 1, target);if (result != -1) {cout << "目标值 " << target << " 在数组中的索引为 " << result << endl;} else {cout << "目标值 " << target << " 不在数组中" << endl;}return 0;
}

代码解析

• 函数参数：arr是有序数组，low和high分别是查找范围的起始和结束位置，target是目标值。
• 循环条件：while (low <= high)，确保查找范围有效。
• 中间值计算：int mid = low + (high - low) / 2;，这种方法可以防止low + high溢出。
• 比较与范围调整：根据中间值与目标值的比较结果，调整查找范围。
• 返回值：如果找到目标值，返回其索引；否则返回-1。

2.2 二分法适用场景

二分法适用于以下场景：

有序数组

二分法的核心是依赖于数组的有序性。只有在数组有序的情况下，二分法才能有效工作。例如，查找一个有序数组中的某个元素，或者确定某个元素在有序数组中的插入位置。

查找效率要求高

当数据量较大且需要快速查找目标值时，二分法的时间复杂度O(log n)相比线性查找的O(n)具有显著优势。例如，在大型数据库中查找记录，或者在实时系统中快速定位数据。

示例场景

假设有一个包含1000000个元素的有序数组，需要查找某个特定值。使用线性查找可能需要最多1000000次比较，而使用二分查找最多只需要20次比较（log2(1000000) ≈ 20），效率提升非常明显。

示例代码

以下是一个二分查找函数，用于在有序数组中查找目标值的插入位置：

#include <iostream>
using namespace std;// 二分查找插入位置函数
int binarySearchInsertPosition(int arr[], int low, int high, int target) {while (low <= high) {int mid = low + (high - low) / 2;if (arr[mid] == target) {return mid; // 找到目标值，返回索引} else if (arr[mid] < target) {low = mid + 1; // 调整查找范围到右半部分} else {high = mid - 1; // 调整查找范围到左半部分}}return low; // 返回插入位置
}int main() {int arr[] = {1, 3, 5, 7, 9, 11, 13, 15}; // 有序数组int target = 6; // 目标值int result = binarySearchInsertPosition(arr, 0, sizeof(arr) / sizeof(arr[0]) - 1, target);cout << "目标值 " << target << " 的插入位置为 " << result << endl;return 0;
}

代码解析

• 函数参数：与二分查找函数类似，但目标是找到目标值的插入位置。
• 循环条件：while (low <= high)，确保查找范围有效。
• 中间值计算：int mid = low + (high - low) / 2;，防止溢出。
• 比较与范围调整：根据中间值与目标值的比较结果，调整查找范围。
• 返回值：如果找到目标值，返回其索引；否则返回目标值应插入的位置。

通过以上分析和示例代码，我们可以更好地理解二分法的核心思想和适用场景。# 3. 二分法函数详解

3.1 初始化左右边界

在二分查找中，初始化左右边界是查找过程的起点，它定义了查找的初始范围。对于一个长度为n的有序数组，左边界low通常初始化为0，表示数组的第一个元素的索引；右边界high初始化为n - 1，表示数组的最后一个元素的索引。正确的初始化能够确保查找范围覆盖整个数组，避免遗漏目标值。

示例代码

int low = 0; // 初始化左边界
int high = n - 1; // 初始化右边界，n为数组长度

代码解析

• 左边界low：表示查找范围的起始位置，初始化为0，确保从数组的第一个元素开始查找。
• 右边界high：表示查找范围的结束位置，初始化为n - 1，确保查找范围覆盖到数组的最后一个元素。

3.2 计算中间值

计算中间值是二分查找的关键步骤，通过将查找范围分成两部分，从而缩小查找范围。中间值的计算公式为mid = low + (high - low) / 2，这种计算方式可以有效防止因low + high过大导致的整数溢出问题。在每次循环中，根据中间值与目标值的比较结果，更新查找范围。

示例代码

int mid = low + (high - low) / 2; // 计算中间值

代码解析

• 防止溢出：直接使用(low + high) / 2可能会导致low + high超出整数范围，而low + (high - low) / 2可以有效避免这种情况。
• 中间值的作用：中间值将查找范围分成两部分，通过与目标值的比较，确定目标值所在的子区间。

3.3 判断与更新区间

在二分查找中，根据中间值与目标值的比较结果，更新查找范围是实现查找的关键。如果中间值等于目标值，查找成功；如果中间值大于目标值，则目标值在左半部分，更新右边界为mid - 1；如果中间值小于目标值，则目标值在右半部分，更新左边界为mid + 1。通过不断更新查找范围，逐步缩小目标值的可能位置，直到找到目标值或查找范围为空。

示例代码

if (arr[mid] == target) {return mid; // 找到目标值，返回索引
} else if (arr[mid] < target) {low = mid + 1; // 目标值在右半部分，更新左边界
} else {high = mid - 1; // 目标值在左半部分，更新右边界
}

代码解析

• 相等时返回索引：如果arr[mid] == target，说明找到了目标值，直接返回中间值的索引mid。
• 目标值在右半部分：如果arr[mid] < target，说明目标值在中间值的右侧，更新左边界为mid + 1。
• 目标值在左半部分：如果arr[mid] > target，说明目标值在中间值的左侧，更新右边界为mid - 1。

通过以上步骤，二分查找能够在有序数组中高效地查找目标值，其时间复杂度为O(log n)，相比线性查找的O(n)具有显著的效率优势。# 4. 示例代码分析

4.1 简单二分查找代码

以下是一个简单的二分查找代码示例，用于在有序数组中查找目标值：

#include <iostream>
using namespace std;// 二分查找函数
int binarySearch(int arr[], int low, int high, int target) {while (low <= high) {int mid = low + (high - low) / 2; // 防止溢出if (arr[mid] == target) {return mid; // 找到目标值，返回索引} else if (arr[mid] < target) {low = mid + 1; // 调整查找范围到右半部分} else {high = mid - 1; // 调整查找范围到左半部分}}return -1; // 未找到目标值，返回-1
}int main() {int arr[] = {1, 3, 5, 7, 9, 11, 13, 15}; // 有序数组int target = 7; // 目标值int result = binarySearch(arr, 0, sizeof(arr) / sizeof(arr[0]) - 1, target);if (result != -1) {cout << "目标值 " << target << " 在数组中的索引为 " << result << endl;} else {cout << "目标值 " << target << " 不在数组中" << endl;}return 0;
}

4.2 代码逻辑解析

4.2.1 函数定义与参数

• 函数定义：int binarySearch(int arr[], int low, int high, int target)
  • arr[]：有序数组，这是二分查找的基础，必须保证数组是有序的。
  • low：查找范围的起始索引，初始值为0。
  • high：查找范围的结束索引，初始值为数组的最后一个元素的索引。
  • target：需要查找的目标值。

4.2.2 循环条件

• 循环条件：while (low <= high)
  • 这个条件确保了查找范围是有效的。只要low小于等于high，就说明查找范围仍然有效，查找过程可以继续。
  • 如果low > high，说明查找范围为空，目标值不存在于数组中，循环结束。

4.2.3 中间值计算

• 中间值计算：int mid = low + (high - low) / 2;
  • 这是二分查找的核心步骤，通过计算中间值将查找范围分成两部分。
  • 使用low + (high - low) / 2而不是(low + high) / 2的原因是防止整数溢出。当low和high都很大时，low + high可能会超出整数范围，导致错误结果。
  • mid是当前查找范围的中间索引，用于与目标值进行比较。

4.2.4 比较与范围调整

• 比较中间值与目标值：
  • if (arr[mid] == target)：如果中间值等于目标值，说明找到了目标值，直接返回中间索引mid。
  • else if (arr[mid] < target)：如果中间值小于目标值，说明目标值在中间值的右侧，更新左边界low = mid + 1。
  • else：如果中间值大于目标值，说明目标值在中间值的左侧，更新右边界high = mid - 1。

4.2.5 返回值

• 返回值：
  • 如果找到目标值，返回目标值的索引mid。
  • 如果未找到目标值，返回-1，表示目标值不在数组中。

4.2.6 主函数

• 主函数：
  • 定义一个有序数组arr，并指定目标值target。
  • 调用binarySearch函数，传入数组、目标值以及查找范围的起始和结束索引。
  • 根据返回值判断目标值是否在数组中，并输出相应的结果。

4.2.7 示例运行

假设数组arr为{1, 3, 5, 7, 9, 11, 13, 15}，目标值target为7：

• 初始范围：low = 0，high = 7。
• 第一次循环：
  • 计算mid = 0 + (7 - 0) / 2 = 3，arr[3] = 7。
  • arr[3] == target，返回mid = 3。
• 输出结果：目标值 7 在数组中的索引为 3。

如果目标值target为6：

• 初始范围：low = 0，high = 7。
• 第一次循环：
  • 计算mid = 0 + (7 - 0) / 2 = 3，arr[3] = 7。
  • arr[3] > target，更新high = mid - 1 = 2。
• 第二次循环：
  • 计算mid = 0 + (2 - 0) / 2 = 1，arr[1] = 3。
  • arr[1] < target，更新low = mid + 1 = 2。
• 第三次循环：
  • 计算mid = 2 + (2 - 2) / 2 = 2，arr[2] = 5。
  • arr[2] < target，更新low = mid + 1 = 3。
• 第四次循环：
  • low = 3，high = 2，low > high，循环结束。
• 返回-1，输出结果：目标值 6 不在数组中。

通过以上分析，我们可以清晰地理解二分查找的逻辑和实现过程。

5. 二分法的广泛应用

5.1 查字典

• 问题描述：在一本字典中查找一个单词的定义。
• 二分法应用：字典中的单词是按字母顺序排列的，可以将字典的页码范围作为查找区间。通过二分法，每次打开中间页码，比较中间页码的单词与目标单词的大小关系，从而缩小查找范围，快速定位到目标单词所在的页码。
• 优势：相比逐页查找，二分法可以显著减少查找时间，提高查找效率。

5.2 静态区间最值问题

• 问题描述：给定一个静态数组，多次查询某个区间内的最大值或最小值。
• 二分法应用：可以使用二分法结合前缀和或后缀和数组来快速求解区间最值。例如，对于求区间最小值，可以先计算每个位置的前缀最小值和后缀最小值，然后通过二分法快速定位到区间内的最小值。
• 优势：在多次查询的情况下，二分法可以快速响应，避免每次都遍历整个区间，提高查询效率。

5.3 特殊的一元三次方程

• 问题描述：求解形如 ( ax^3 + bx^2 + cx + d = 0 ) 的一元三次方程的实数根。
• 二分法应用：在一元三次方程中，可以通过二分法找到方程的实数根。首先确定一个包含实数根的区间，然后通过不断二分区间，计算中间值处的函数值，根据函数值的符号变化来缩小区间，直到找到满足精度要求的实数根。
• 优势：二分法可以高效地求解实数根，尤其适用于方程的实数根在某个已知区间内的情况。

5.4 [模板] 快速幂

• 问题描述：计算 ( a^b ) 的值，其中 ( a ) 和 ( b ) 是整数，且 ( b ) 可能非常大。
• 二分法应用：快速幂算法本质上是利用二分的思想来减少乘法运算的次数。通过将指数 ( b ) 分解为二进制表示，每次只计算 ( a ) 的平方，然后根据二进制位的值决定是否将当前结果乘到最终结果中，从而将时间复杂度从 ( O(b) ) 降低到 ( O(\log b) )。
• 优势：快速幂算法在处理大指数幂运算时效率极高，尤其适用于编程竞赛和实际应用中的大数幂运算。