二分问题，

1. 什么是二分查找二分查找Binary Search是一种在有序数组中查找目标值的高效算法。它的核心思想是每次将搜索范围缩小一半因此时间复杂度为 O(log n)远优于线性查找的 O(n)。2. 算法原理二分查找的基本步骤如下初始化左右指针分别指向数组的起始位置和结束位置。计算中间位置 mid (left right) / 2。比较中间元素与目标值如果中间元素等于目标值直接返回下标。如果中间元素大于目标值说明目标值在左半部分将右指针移动到 mid - 1。如果中间元素小于目标值说明目标值在右半部分将左指针移动到 mid 1。重复上述步骤直到左指针大于右指针此时说明数组中不存在目标值。这里需要特别区分左右区间的更新规则右指针更新搜索左半区间当中间元素大于目标值时说明目标值只可能出现在 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 vectorint 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() { vectorint 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() { vectorint 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 vectorint woods, int mid, int k) { int count 0; for (int len : woods) { count len / mid; } return count k; } int main() { vectorint 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; }运行结果如下每段最大长度: 5min(max)模板int l 下界, r 上界; while(l r) { int mid (l r) / 2; if(check(mid)) { r mid; } else { l mid 1; } } // ans lmax(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. 变体与应用二分查找有很多变体常见的有查找第一个等于目标值的位置用于处理重复元素。查找最后一个等于目标值的位置同样用于重复元素场景。查找第一个大于等于目标值的位置可用于插入位置的确定。查找最后一个小于等于目标值的位置常用于区间查询。此外二分查找的思想也广泛应用于旋转数组查找、求平方根、二分答案等场景。