C++二分查找

一、模板①：向下取整（mid = (l + r) >> 1）

while (l < r) {int mid = l + r >> 1; // 等价于 (l + r) / 2（向下取整）if (check(mid)) r = mid; // 保留左半区else l = mid + 1;        // 舍弃左半区
}

适用场景

1. 查找左边界（最小值）

   • 例如：在有序数组中找到 第一个大于等于目标值 的位置
   • 逻辑：当 check(mid) 满足条件时，说明目标值可能在左半区（包括 mid），因此右边界 r 缩小到 mid；否则，左边界 l 移动到 mid + 1。
   • 关键特征：区间收缩时 保留左半区，mid 向下取整可避免死循环

2. 寻找满足条件的最小值

   • 例如：求满足 x² ≤ target 的最大整数 x（即平方根的整数部分）
   • 原因：向下取整确保中间值偏向左侧，逐步逼近最小可行解。

---

二、模板②：向上取整（mid = (l + r + 1) >> 1）

while (l < r) {int mid = l + r + 1 >> 1; // 等价于 (l + r + 1) / 2（向上取整）if (check(mid)) l = mid;   // 保留右半区else r = mid - 1;         // 舍弃右半区
}

适用场景

1. 查找右边界（最大值）

   • 例如：在有序数组中找到 最后一个小于等于目标值 的位置
   • 逻辑：当 check(mid) 满足条件时，说明目标值可能在右半区（包括 mid），因此左边界 l 移动到 mid；否则，右边界 r 缩小到 mid - 1。
   • 关键特征：区间收缩时 保留右半区，mid 向上取整可防止循环卡死

2. 寻找满足条件的最大值

   • 例如：求巧克力切割的最大边长，使得总块数满足要求
   • 原因：向上取整确保中间值偏向右侧，逐步逼近最大可行解。

---

三、核心区别与选择依据

特征	模板①（向下取整）	模板②（向上取整）
mid 计算	mid = (l + r) / 2	mid = (l + r + 1) / 2
区间收缩	保留左半区（r = mid）	保留右半区（l = mid）
适用方向	左边界、最小值、左侧优先	右边界、最大值、右侧优先
防死循环	确保 l 和 r 逐步靠近	避免 l 和 r 无法缩小范围

选择原则

1. 分析问题目标：明确是找左边界还是右边界，是求最小值还是最大值。
2. 观察区间更新：若更新 l = mid，则必须向上取整；若更新 r = mid，则需向下取整
3. 验证边界条件：通过极端用例（如 l 和 r 相邻时）检查是否可能陷入死循环。

例题：

问题描述

小蓝有一个神奇的炉子用于将普通金属 O 冶炼成为一种特殊金属 X。这个炉子有一个称作转换率的属性 V，V 是一个正整数，这意味着消耗 V 个普通金属 O 恰好可以冶炼出一个特殊金属 XX，当普通金属 O 的数目不足 V 时，无法继续冶炼。

现在给出了 N 条冶炼记录，每条记录中包含两个整数 A 和 B，这表示本次投入了 A 个普通金属 O，最终冶炼出了 B 个特殊金属 X。每条记录都是独立的，这意味着上一次没消耗完的普通金属 O 不会累加到下一次的冶炼当中。

根据这 N 条冶炼记录，请你推测出转换率 V 的最小值和最大值分别可能是多少，题目保证评测数据不存在无解的情况。

输入格式

第一行一个整数 N，表示冶炼记录的数目。

接下来输入 N 行，每行两个整数 A、B，含义如题目所述。

输出格式

输出两个整数，分别表示 V 可能的最小值和最大值，中间用空格分开。

#include<bits/stdc++.h>  // 包含所有标准库头文件（实际工程中不建议使用）#define rep(i, a, b) for(int i = a; i < b; i++)  // 简化循环的宏定义using namespace std;
const int N = 1e4 + 10;  // 定义常量（但代码中未实际使用）
int n;// 二分查找函数：寻找满足条件的最大/最小值[6,8](@ref)
int get(int a, int b) 
{int l = 1, r = a;  // 初始化搜索范围为[1, a]while(l < r)  // 标准二分查找结构[7](@ref){int mid = l + r >> 1;  // 等效于(l + r)/2（向下取整）// 核心判断条件：当a/mid <= b时，收缩右边界if(a / mid <= b)r = mid;    // 满足条件时尝试更小的值else l = mid + 1; // 不满足条件时增大下界}return r;  // 最终收敛到满足条件的最小值[8](@ref)
}int main()
{cin >> n;  // 读取输入的对数// 初始化极值（minv为下限，maxv为上限）int minv = 1;         // 最小值的初始下界int maxv = 1e9;       // 最大值的初始上界int a, b;rep(i, 0, n)  // 遍历每个输入对{scanf("%d%d", &a, &b);// 关键逻辑：对多个区间取交集[10,11](@ref)// 更新最小值下限（取所有区间的最大左端点）minv = max(minv, get(a, b));// 更新最大值上限（取所有区间的最小右端点）maxv = min(maxv, get(a, b - 1) - 1);}// 输出最终的交集区间cout << minv << " " << maxv;return 0;
}

问题描述

儿童节那天有 K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。

小明一共有 N 块巧克力，其中第 i 块是 Hi×Wi 的方格组成的长方形。为了公平起见，

小明需要从这 N块巧克力中切出 K 块巧克力分给小朋友们。切出的巧克力需要满足：

1. 形状是正方形，边长是整数;

2. 大小相同;

例如一块 6×5 的巧克力可以切出 6 块 2×2 的巧克力或者 2 块 3×3 的巧克力。

当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？

输入描述

第一行包含两个整数 N,K (1≤N,K≤105)。

以下 N 行每行包含两个整数 Hi,Wi (1≤Hi,Wi≤105)。

输入保证每位小朋友至少能获得一块 1x1 的巧克力。

输出描述

输出切出的正方形巧克力最大可能的边长。

#include<bits/stdc++.h>  
using namespace std; const int N=1e5+5; // 定义常数N，表示矩形数量的上限  
int h[N],w[N]; // 定义两个数组，分别存储每个矩形的高和宽  
int n,k,m; // 定义变量n表示矩形数量，k表示目标正方形数量，m用于存储矩形尺寸的最大值  // 定义一个检查函数，判断给定的正方形边长mid是否满足条件  
bool check(int mid){  int sum=0; // 用于计算可以切割出的正方形数量  for(int i=0;i<n;i++){ // 遍历每个矩形  sum+=(h[i]/mid)*(w[i]/mid); // 计算当前矩形可以切割出的正方形数量，并累加到sum中  }  if(sum>=k){ // 如果满足至少k个正方形的要求  return true;  // 返回true  }else{  return false; // 否则返回false  }  
}  void solve(){  int l=1,r=m; // 定义二分查找的左右边界，l为最小可能边长1，r为矩形的最大尺寸  while(l<r){ // 当左边界小于右边界时，继续二分查找  int mid=l+(r-l)/2; // 计算中点，并向上取整（因为l+r可能是奇数）  if(check(mid)){ // 如果mid满足条件  l=mid; // 更新左边界为mid，继续寻找更小的满足条件的边长  }else{  r=mid-1; // 否则，更新右边界为mid-1，寻找更大的边长  }  }  cout<<l<<'\n'; // 输出最小的满足条件的边长  
}   signed main(){  ios::sync_with_stdio(0); // 取消C++和C的输入输出同步，加快输入输出速度  cin.tie(0); // 解除cin与cout的绑定，加快输入输出速度  cout.tie(0);	  cin>>n>>k; // 输入矩形数量n和目标正方形数量k  for(int i=0;i<n;i++){ // 遍历每个矩形  cin>>h[i]>>w[i]; // 输入矩形的高和宽  m=max(h[i],m); // 更新m为矩形尺寸的最大值  m=max(w[i],m);  }  solve(); return 0;  
}