二分问题，

1. 什么是二分查找

二分查找（Binary Search）是一种在有序数组中查找目标值的高效算法。它的核心思想是每次将搜索范围缩小一半，因此时间复杂度为 O(log n)，远优于线性查找的 O(n)。

2. 算法原理

二分查找的基本步骤如下：

1. 初始化左右指针，分别指向数组的起始位置和结束位置。
2. 计算中间位置 mid = (left + right) / 2。
3. 比较中间元素与目标值：
   • 如果中间元素等于目标值，直接返回下标。
   • 如果中间元素大于目标值，说明目标值在左半部分，将右指针移动到 mid - 1。
   • 如果中间元素小于目标值，说明目标值在右半部分，将左指针移动到 mid + 1。
4. 重复上述步骤，直到左指针大于右指针，此时说明数组中不存在目标值。

这里需要特别区分左右区间的更新规则：

• 右指针更新（搜索左半区间）：当中间元素大于目标值时，说明目标值只可能出现在 mid 左侧，此时将右指针更新为 mid - 1，即 right = mid - 1，搜索区间变为 [left, mid - 1]。
• 左指针更新（搜索右半区间）：当中间元素小于目标值时，说明目标值只可能出现在 mid 右侧，此时将左指针更新为 mid + 1，即 left = mid + 1，搜索区间变为 [mid + 1, right]。

左右区间的划分是二分查找的核心：每次迭代都会根据中间元素与目标值的大小关系，将搜索范围精确地收缩到左半区间或右半区间，从而保证每次都能排除一半的候选元素。

左右区间的更新伪代码如下：

// 搜索左半区间：目标值在 mid 左侧 if (arr[mid] > target) { right = mid - 1; // 区间收缩为 [left, mid - 1] } // 搜索右半区间：目标值在 mid 右侧 if (arr[mid] < target) { left = mid + 1; // 区间收缩为 [mid + 1, right] }

3. 代码实现

下面给出一个 C++ 实现的基础二分查找示例：

#include <iostream> #include <vector> using namespace std; int binarySearch(const vector<int>& arr, int target) { int left = 0; int right = arr.size() - 1; while (left <= right) { int mid = left + (right - left) / 2; // 防止溢出 if (arr[mid] == target) { return mid; } else if (arr[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1; // 未找到 } int main() { vector<int> arr = {1, 3, 5, 7, 9, 11}; int target = 7; int result = binarySearch(arr, target); cout << "目标值下标: " << result << endl; return 0; }

4. 注意事项

• 数组必须有序：二分查找的前提是数组已经按升序或降序排列，否则结果不正确。
• 边界处理：注意 left 和 right 的更新方式，避免死循环或越界。
• 防止溢出：计算 mid 时使用 left + (right - left) / 2，避免 left + right 溢出。
• 适用场景：二分查找适合静态数据、频繁查询的场景；如果数据频繁插入删除，维护有序性的成本较高。

6. STL 中的二分查找函数

C++ 标准库（STL）在<algorithm>头文件中提供了多个二分查找相关函数，它们都要求数组或容器已经有序。下面介绍最常用的几个：

• binary_search：判断目标值是否存在，返回 bool。
• lower_bound：返回第一个大于等于目标值的迭代器（即第一个不小于 target 的位置）。
• upper_bound：返回第一个大于目标值的迭代器。
• equal_range：同时返回 lower_bound 和 upper_bound 的结果，用于确定目标值的完整区间。

下面给出一个使用 STL 二分函数的完整示例：

#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { vector<int> arr = {1, 3, 5, 7, 7, 9, 11}; int target = 7; // 1. binary_search：判断是否存在 bool exists = binary_search(arr.begin(), arr.end(), target); cout << "是否存在 " << target << ": " << (exists ? "是" : "否") << endl; // 2. lower_bound：第一个 >= target 的位置 auto it1 = lower_bound(arr.begin(), arr.end(), target); cout << "第一个 >= " << target << " 的下标: " << (it1 - arr.begin()) << endl; // 3. upper_bound：第一个 > target 的位置 auto it2 = upper_bound(arr.begin(), arr.end(), target); cout << "第一个 > " << target << " 的下标: " << (it2 - arr.begin()) << endl; // 4. equal_range：同时获取 [lower, upper) 区间 auto range = equal_range(arr.begin(), arr.end(), target); cout << "等于 " << target << " 的区间: [" << (range.first - arr.begin()) << ", " << (range.second - arr.begin()) << ")" << endl; return 0; }

运行结果如下：

是否存在 7: 是 第一个 >= 7 的下标: 3 第一个 > 7 的下标: 5 等于 7 的区间: [3, 5)

需要特别注意的是，lower_bound和upper_bound返回的是迭代器，通过it - arr.begin()可以转换为下标；equal_range返回的区间是左闭右开[first, second)，其中second - first就是目标值在数组中出现的次数。

7. 二分答案

二分答案是一种利用二分思想解决最优化问题的常用技巧。它的核心思路是：将「求最优解」转化为「判断某个候选值是否可行」，然后在一个单调的取值范围内不断二分，逼近最优解。

二分答案通常需要满足以下两个前提：

• 答案具有单调性：如果某个值可行，那么比它更优（或更差）的值也一定可行，即判断结果随取值单调变化。
• 存在明确的可行判断函数：能够快速判断一个候选值是否满足题目要求。

二分答案的通用伪代码如下：

// 判断候选值 mid 是否可行 bool check(int mid) { // 根据题目要求实现判断逻辑 return true; // 或 false } // 二分答案主流程 int left = 最小值; int right = 最大值; while (left <= right) { int mid = left + (right - left) / 2; if (check(mid)) { // mid 可行，尝试更优的方向 left = mid + 1; // 或 right = mid - 1，取决于求最大值还是最小值 } else { // mid 不可行，收缩到可行区间 right = mid - 1; // 或 left = mid + 1 } }

下面以经典的「木材切割问题」为例：给定 n 段木材的长度，要求切割成至少 k 段长度相同的木材，求每段的最大可能长度。

#include <iostream> #include <vector> using namespace std; // 判断每段长度为 mid 时能否切出至少 k 段 bool check(const vector<int>& woods, int mid, int k) { int count = 0; for (int len : woods) { count += len / mid; } return count >= k; } int main() { vector<int> woods = {10, 24, 15}; int k = 7; int left = 1; // 每段长度至少为 1 int right = 24; // 最长木材的长度 int ans = 0; while (left <= right) { int mid = left + (right - left) / 2; if (check(woods, mid, k)) { ans = mid; // mid 可行，记录并尝试更长 left = mid + 1; } else { right = mid - 1; } } cout << "每段最大长度: " << ans << endl; return 0; }

运行结果如下：

每段最大长度: 5

min(max)模板

int l = 下界, r = 上界; while(l < r) { int mid = (l + r) / 2; if(check(mid)) { r = mid; } else { l = mid + 1; } } // ans = l

max(min)模板

int l = 下界, r = 上界; while(l < r) { int mid = (l + r + 1) / 2; // 向上取整！防止死循环 if(check(mid)) { l = mid; } else { r = mid - 1; } } // ans = l

二分答案广泛应用于求最大值最小化、最小值最大化、浮点数精度逼近等问题，例如「分巧克力」「跳石头」「机器人跳跃」等经典题目。

5. 变体与应用

二分查找有很多变体，常见的有：

• 查找第一个等于目标值的位置：用于处理重复元素。
• 查找最后一个等于目标值的位置：同样用于重复元素场景。
• 查找第一个大于等于目标值的位置：可用于插入位置的确定。
• 查找最后一个小于等于目标值的位置：常用于区间查询。

此外，二分查找的思想也广泛应用于旋转数组查找、求平方根、二分答案等场景。