一、二分查找（binary search）
1.引入
二分法（Bisection method）是一种在单调有序的集合或函数中查找解的高效算法。
其核心思想是：
- 每次将搜索空间分为两部分
- 通过判断解的位置舍弃一半空间
- 逐步缩小范围直至找到目标
时间复杂度分析：
- 整数域：对于长度为N的区间，需要O(logN)次确定分界点
- 实数域：通过判断区间长度(R-L)是否达到精度要求(如R-L≥eps)
- 指定次数t：最终区间长度为初始长度L除以2^t
- 总复杂度：O(二分次数 × 单次判定复杂度)
我们思考这么一个问题：
假设你有一本1000页的英文字典，要查找单词”algorithm“的页码：
- 方法一：从第1页开始，一页一页翻找
- 方法二：随机翻开一页，根据字母顺序决定往前或往后翻
- 方法三：每次都翻到中间位置，根据比较结果排除一半页面
显然，第三种方法最高效——这就是二分查找的核心思想。
2.对比线性搜索
// 线性搜索：O(n)时间复杂度
int linear_search(int arr[], int n, int target) {
for (int i = 0; i < n; i++) {
if (arr[i] == target) {
return i;
}
}
return -1;
}- 当n=1,000,000时，最坏情况需要比较1,000,000次
- 对于有序数据，这种”盲目”的搜索存在巨大优化空间
而二分查找算法基于分治思想，将问题规模每次减半：
初始：在[0, n-1]区间查找
第1步：比较中间元素，排除一半区间
第2步：在剩下的一半区间重复此过程
…
直至找到目标或区间为空
查找目标值 23 在排序数组中的位置
数组：[2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
索引： 0 1 2 3 4 5 6 7 8 9
第1轮：left=0, right=9, mid=4 → arr[4]=16 < 23 → 查找右半区 [5,9]
第2轮：left=5, right=9, mid=7 → arr[7]=56 > 23 → 查找左半区 [5,6]
第3轮：left=5, right=6, mid=5 → arr[5]=23 == 23 → 找到目标！
只用了3次比较，线性搜索需要6次。
下表为对比二分对于线性搜索的复杂度：
| 数据规模n | 线性搜索O(n) | 二分查找O(log₂n) |
|---|---|---|
| 1,000 | 1,000次比较 | 10次比较 |
| 1,000,000 | 1,000,000次 | 20次比较 |
| 1,000,000,000 | 10⁹次 | 30次比较 |
指数级的效率提升！
3.实现模板
int binary_search_first(int l, int r)
{
int ans = r + 1; // 初始化为"无解"状态（超出范围）
while (l <= r)
{
int mid = (l + r) >> 1; // 防止溢出的写法，普遍最优，快速幂有提
// 核心逻辑：如果mid满足条件，记录答案并向左继续寻找更小的
// check_first函数为自定义判断函数
if (check_first(mid))
{
ans = mid; // 记录当前可行解
r = mid - 1; // 向左缩小范围，寻找更小的解
}
else
{
l = mid + 1; // 向右扩大范围
}
}
return ans;
}
int binary_search_last(int l, int r)
{
int ans = l - 1; // 初始化为"无解"状态（小于左边界）
while (l <= r)
{
int mid = (l + r) >> 1;
// 核心逻辑：如果mid满足条件，记录答案并向右继续寻找更大的
// check_last函数为自定义判断函数
if (check_last(mid))
{
ans = mid; // 记录当前可行解
l = mid + 1; // 向右缩小范围，寻找更大的解
}
else
{
r = mid - 1; // 向左扩大范围
}
}
return ans;
}
double binary_search_real(double l, double r)
{
// 确保左边界小于右边界
if (l > r)
{
swap(l, r);
}
// 不断二分直到区间足够小，eps为自定精度要求
while (r - l > eps)
{
double mid = (l + r) / 2;
if (check_real(mid))
{
// 如果mid满足条件，尝试更小的值
r = mid;
}
else
{
// 如果mid不满足条件，尝试更大的值
l = mid;
}
}
return l; // 返回左边界作为近似解
}对于二分查找在STL库中的快捷使用请看算法象限·查找类算法的有序查找。
二、二分答案
1.什么是二分答案
1.1 核心思想
二分答案不是一种新算法，而是二分查找的一种应用方式。它将最优化问题转化为判定性问题：
常规思路：尝试所有可能的答案 → 判断是否可行 → 找到最优解
二分答案：猜测一个答案 → 判断是否可行 → 调整猜测范围 → 快速找到最优解
1.2 适用问题特征
- 最大值最小化（Minimizing the Maximum）
- 例子：把数组分成k段，使得最大段的和最小
- 最小值最大化（Maximizing the Minimum）
- 例子：分配资源，使得最小资源量尽可能大
2.二分答案模板
int binary_search_min_answer(int l, int r) //模板1
{
int answer = -1; // 存储最终答案
while (l <= r)
{
int mid = (l + r) >> 1;
if (check(mid))
{
// mid可行，尝试寻找更小的可行解
answer = mid; // 记录当前可行解
r = mid - 1; // 向左搜索，尝试更小的值
}
else
{
// mid不可行，需要增大
l = mid + 1; // 向右搜索
}
}
return answer;
}
int binary_search_max_answer(int l, int r) //模板2
{
int answer = -1; // 存储最终答案
while (l <= r)
{
int mid = (l + r) >> 1;
if (check(mid))
{
// mid可行，尝试寻找更大的可行解
answer = mid; // 记录当前可行解
l = mid + 1; // 向右搜索，尝试更大的值
}
else
{
// mid不可行，需要减小
r = mid - 1; // 向左搜索
}
}
return answer;
}我们不难发现，其实二分答案的代码与之前二分查找别无二致，核心还是在于怎么处理边界问题。
三、二分核心要点
1.如何确定二分的边界
// 通常有三种方式确定边界：
// 1. 理论边界（推荐）
int l = 最大单个元素值; // 最小可能值
int r = 所有元素总和; // 最大可能值
// 2. 数据范围边界
int l = 1; // 根据题目要求
int r = 1e9; // 根据数据范围
// 3. 极值边界
int l = 0;
int r = INT_MAX;2.如何设计Check函数
Check函数是二分答案的核心，设计时需要：
- 正确性：准确判断mid是否可行
- 高效性：通常是O(n)或O(n log n)复杂度
- 边界处理：考虑极端情况
3.选择哪个模板
- 模板1：当问题是”最小值”时使用（如：最小运载能力）
- 模板2：当问题是”最大值”时使用（如：最大能分配的最小值）
示例：
weights = [1,2,3,4,5,6,7,8,9,10], days = 5
搜索过程：
left=10, right=55
mid=32 → 需要2天 → 可行 → right=31
mid=20 → 需要3天 → 可行 → right=19
mid=14 → 需要4天 → 可行 → right=13
mid=11 → 需要5天 → 可行 → right=10
mid=10 → 需要6天 → 不可行 → left=11
最终答案：11
四、常见问题及技巧
1.为什么二分答案可行
因为答案具有单调性：如果值X可行，那么所有≥X的值都可行（对于最小化问题）。
2.调试技巧
- 打印中间结果：查看每次mid和check结果
- 验证最终答案：用找到的答案重新验证
- 边界测试：测试最小/最大输入
3.总结
二分答案的本质是：
- 问题转化：最优化问题 → 判定性问题
- 利用单调性：答案区间具有单调性质
- 二分加速：O(n)的判定 + O(log n)的搜索
掌握二分答案的关键是：
- 准确设计Check函数
- 合理确定搜索边界
- 正确选择模板方向
二分答案的难点不在二分本身，而在Check函数的设计和问题转化。
等我有时间精选几道二分好题供大家真正上手二分查找和答案。
