二分法（Bisection Method）

二分法是一种非常基础且通用的数值计算方法，主要用于求解方程的根（即找到使函数值为 0 的点）。

核心原理：夹逼定理

二分法的理论基础是连续函数的介值定理（Intermediate Value Theorem）。

简单来说：

如果一个函数 f(x) 在区间 [a,b] 上是连续的，并且 f(a) 和 f(b) 的符号相反（即一正一负，意味着图像穿过了 x 轴），那么在这个区间内部至少存在一个点 c，使得 f(c)=0。

此时，我们只需要不断的找中心点，通过比较c在中心点左还是右来减小区间，最终确定c的具体位置。

从数学角度来讲，由于这个方法的鲁棒性强，因此我们可以把它当作解决求根的最后一个方案。

二分查找

核心思想：在有序的数组里，每次砍掉一半不可能的区间，快速找到目标。

前提：数组必须有序。

步骤：

1. 设左边界 left，右边界 right
2. 取中点 mid = (left + right) / 2
3. 比较 a[mid] 和目标值：
   • 等于 → 找到了
   • 小于 → 答案在右边，left = mid + 1
   • 大于 → 答案在左边，right = mid - 1
4. 重复直到找到或区间为空

时间复杂度：O(log n)

100 万的数据最多查 20 次。

应用场景

• 找某个数是否存在
• 找第一个 ≥ x 的位置（lower_bound）
• 找最后一个 ≤ x 的位置

二分答案

核心思想：答案本身具有单调性，先二分答案的值，再通过函数判断该值是否正确。

步骤：

• 最大的最小 xxx
• 最小的最大 xxx
• 满足条件的最小值
• 满足条件的最大值
• 分割数组、最小最大距离、最小花费等

应用场景

1. 先确定题目要求的内容
2. 根据求的内容确定答案的区间[L,R]
3. 根据当前区间，二分出答案mid
4. 写一个check(mid)函数：
   • 返回true：尝试更优答案
   • 返回false：调整方向
5. 通过不断缩小区间最后确定最优解

代码相关

确定答案范围：L和R
初始化ans：-1、L或R
初始化mid：作为区间中心点

while (L <= R) { 
    mid = L + (R - L) / 2;
    if (check(mid)) {  // 满足条件
        ans = mid;
        R = mid - 1;  // 尝试更小
    }
    else {
        L = mid + 1;   // 不够，要更大
    }
}

算法库相关

查找value是否存在

• bool binary_search(first, last, value);

查找第一个大于等于value的位置

• iterator lower_bound(first, last, value);

查找第一个大于value的位置

• iterator upper_bound(first, last, value);

同时返回lower和upper

• pair<iterator, iterator> equal_range(…);
• 常用于求value出现的次数