最小值问题

while(l<r){
    int mid=l+(r-l)>>1; 
    if(check(mid))r=mid;  
    else l=mid+1;          
}

最大值问题

while(l<r){
    int mid=l+(r-l+1)>>1;  
    if(check(mid))l=mid;   
    else r=mid-1;         
}

浮点数二分

const double MIN=1e-6;//精度控制（通常比题目要求高2位）
while(r-l>MIN) {
    double mid=(l+r)>>1;
    if(check(mid))r=mid;
    else l=mid;
}
//输出l或r均可（差值<MIN）

一、核心思想

减治思想：通过中间值mid将搜索范围一分为二，每次排除一半不可能的解

三大前提：

单调性（有序性）

存在明确边界

可构造判断函数check(mid)

二、整数二分模板

模板A（找左边界）：

while (l < r) {
    int mid = l + (r - l) / 2;
    if (check(mid)) r = mid;
    else l = mid + 1;
}
// 输出l或r

适用：求第一个满足条件的值（如：升序数组中≥x的最小下标）

模板B（找右边界）：

while (l < r) {
    int mid = l + (r - l + 1) / 2;
    if (check(mid)) l = mid;
    else r = mid - 1;
}
// 输出l或r

适用：求最后一个满足条件的值（如：升序数组中≤x的最大下标）

三、浮点数二分模板

const double eps = 1e-8;
while (r - l > eps) {
    double mid = (l + r) / 2;
    if (check(mid)) r = mid;
    else l = mid;
}
// 输出(l + r)/2

关键点：

精度控制：eps通常取题目要求精度的1/100

应用场景：平方根、方程求根等

四、经典应用场景

查找类问题：

有序数组查找（lower_bound/upper_bound）

旋转数组找最小值（如LeetCode 153）

答案二分：

最大值最小化（如：跳石头问题）

最小值最大化（如：分披萨问题）

数学计算：

求平方根（保留小数）

解非线性方程

五、易错点清单

死循环：模板B必须mid = l + (r - l + 1)/2

边界溢出：避免(l + r)/2写法

精度陷阱：浮点数比较用差值而非==

初始边界：需覆盖所有可能解