[算法学习]模板-二分

根据二分性质, 某一范围的抽象值可划分为两种情况:
case1 : false, … , false, true, …, true
最后一个 false 被称为左分界点, 第一个 true 被称为右分界点
case2 : true, …, true, false, … , false
最后一个 true 被称为左分界点, 第一个 false 被称为右分界点

check(x) 为二分性质判别函数, 输入为某个值 x, 输出为 true/false, 功能为判断值 x 是否符合二分性质
例:
数组 [1, 2, 3, 4], 二分性质: >= 3
于是 [false, false, true, true]

模板一

求 case 1 时的右分界点

int l = 左边界, r = 右边界
while(l < r)
{
    int mid = l + r >> 1;	// 右分界点, 向左取整
    if(check(mid)) r = mid;	
    else l = mid + 1;		
}
if(check(l)) return l;		// 查找成功
return -1;                  // -1 定义为查找失败应返回的值

模板二

求 case 2 时的左分界点

int l = 左边界, r = 右边界
while(l < r)
{
    int mid = l + r + 1 >> 1;// 左分界点, 向右取整
    if(check(mid)) l = mid;	
    else r = mid - 1;		
}
if(check(l)) return l;		// 查找成功
return -1;                  // -1 定义为查找失败应返回的值

模板三（相等）

int l = 左边界, r = 右边界
while(l<=r)// 注意这里是 <=
{
    int mid = l+r>>1;
    if(nums[mid]<target)l=mid+1;
    else if(nums[mid]>target)r=mid-1;
    else return mid;
}

🚀 实战进阶补丁 (Hotfix)

(注：以下为应对蓝桥杯极端数据和特殊题型的降维打击补丁)

🛠️ 补丁 1：极其阴险的“溢出刺客”防范

当数据范围极大（如 l, r ≈ 2 *10^9 时），l + r 在移位前就会爆 int 变成负数，导致数组越界（RE）。

• 物理级防御：直接把 l, r, mid 声明为 long long。
• 算法级防御：改写求中点公式。

C++

// 绝对安全的求中点写法，彻底掐死溢出可能
int mid = l + ((r - l) >> 1); 

🛠️ 补丁 2：蓝桥杯合法的官方外挂 (STL)

在对纯数字数组进行二分查找时，直接调用 C++ 标准库，避免手写边界失误（需 #include <algorithm>）：

• std::lower_bound(a + 1, a + n + 1, target)：

  返回指向数组中第一个大于或等于 target 的元素的指针（等价于模板一）。

• std::upper_bound(a + 1, a + n + 1, target)：

  返回指向数组中第一个严格大于 target 的元素的指针。

  (技巧：由于返回的是指针，通常在末尾减去数组首地址 a，即可获得其具体的下标索引。)

🛠️ 补丁 3：实数二分（浮点数切割模型）

针对“切割绳子”、“计算最大平均值”等答案包含小数的题型。

由于浮点数没有“相邻”的概念，彻底抛弃 +1 和 -1，直接利用精度差 1e-5 或固定的循环次数来强制逼近。

double l = 0, r = 1e9; // 视题目数据范围而定
// 直接规定精度差，比如 1e-5。若题目要求保留 2 位小数，精度一般多开 2 位即 1e-4。
while(r - l > 1e-5) 
{ 
    double mid = (l + r) / 2;
    if(check(mid)) l = mid;  // 实数二分，绝不加减 1
    else r = mid;
}
// 最终 l 和 r 极度接近，输出 l 即可

🚀 终极架构：二分答案 (Binary Search on Answer)

如果说“二分查找”是在已知的数组里找位置，那么“二分答案”就是凭空猜一个数值。
它的核心思想是：答案的范围已知（有一个明显的上下界），且答案满足单调性。我们不再去硬算答案，而是直接猜一个 mid，然后写一个 check(mid) 函数去验证这个 mid 合不合法。

⚙️ 核心引擎：check(mid) 贪心状态机

二分答案的灵魂 10% 在二分模板，90% 在 check 函数。
check(mid) 本质上是一个 $O(N)$ 的贪心状态机，它的标准运行图纸如下：

1. 设立阈值：将传入的 mid 作为物理极限（最大容量、最短距离等）。
2. 状态遍历：使用 for 循环遍历所有元素，累加状态。
3. 触发与重置：一旦当前状态突破了 mid 的限制，立刻强行阻断，执行动作（如：新开一个箱子、移走一块石头），并重置当前状态。
4. 终极校验：遍历结束后，比对执行动作的总次数是否超出了题目给定的配额（如：箱子总数 $M$、最多移走 $M$ 块）。

⚔️ 两大经典业务模型

模型一：最大值最小化 (Minimize the Maximum)

• 业务场景：把数组分成 $M$ 段，让和最大的一段尽可能小（如：流水线打包、数列分段）。
• 单调性：false, false, true, true。mid 越大越容易满足要求。
• 搜寻目标：寻找第一个 true（套用模板一）。
• 收缩逻辑：

    int mid = l + (r - l) / 2;
    if(check(mid)) r = mid; // 合格，尝试更小的极限
    else l = mid + 1;       // 不合格，箱子塞爆了，必须放宽极限
  
  #### 模型二：最小值最大化 (Maximize the Minimum)
  
  - **业务场景**：移走 $M$ 块石头，让最短的跳跃距离尽可能大（如：跳石头、分配基站）。
  
  - **单调性**：`true, true, true, false, false`。`mid` 越小越容易满足要求。
  
  - **搜寻目标**：寻找**最后一个 `true`**（套用模板二）。
  
  - **收缩逻辑**：
  
    ```c++
    int mid = l + (r - l + 1) / 2; // 必须向上取整，防死循环！
    if(check(mid)) l = mid;        // 合格，尝试挑战更大的距离！
    else r = mid - 1;              // 不合格，石头移超标了，必须缩短距离

💣 高危内存溢出与边界暗雷 (Edge Cases)

1. 起点与终点的隐蔽性：题目往往只给中间的元素，必须手动将起点（通常为 0）和终点（$L$）加入数组或循环逻辑中，否则最后一段的校验将彻底丢失！
2. 极小值陷阱 ($N=0$)：当数组为空（如起点和终点之间没有元素）时，原数组的距离计算逻辑会崩溃。严禁在下界 l 赋值时使用求数组相邻元素最小值的逻辑，请直接无脑使用物理极小值（如 l = 0 或 l = 1）。
3. 隐式类型转换截断：主函数虽然使用了 long long mid 传参，但如果 check(int mid) 忘记同步修改参数类型，会导致超出 32 位的超大数据被静默截断，引发极其诡异的 WA。所有相关变量必须统一类型！

💡 灵魂叩问：到底怎么构思 check(mid)？

很多初学者拿到题，根本不知道 check(mid) 里面该写什么。记住核心心法：变量降维打击！

原题目通常有两个互相牵扯的变量（比如：“最小跳跃距离” 和 “最多移走 $M$ 个石头”）。
我们的做法是：强行固定一个，验证另一个。

1. mid 就是绝对标准：我们假设 mid 就是最终的那个“最小距离/最大重量”。在 check 函数里，不管付出什么代价，都必须强行维护这个标准。
2. 拿另一个限制条件做最后审查：

// 示例：检查“移除不超过 m 个石头后，最小距离能否 ≥ mid”
// 心法：mid 是我们在外部二分遍历的“绝对标准”，我们只用拿 m 做最后审查！
bool check(int mid) {
    int cost = 0; // 记录为了维持 mid 这个标准，我们付出了多少代价（如：移走石头的数量）
    
    // ... 遍历数组，一旦发现不符合 mid 标准的，强行干预并增加 cost
    
    // 最终，拿着我们付出的总代价 cost，去和老板给的配额 m 对账！
    return cost <= m; 
}