思路：
如何优雅的处理边界条件？
1. 左边界、右边界的更新
先看一个例子：给定一个排好序的整数数组a，数组中可能存在重复元素。给定数组中的一个值target，求出它最后出现的位置。
例如数组a为：[1 3 3 3 5],目标值target = 3。a中最后一个等于3的元素为：a[3],所以结果为3。
最容易想到的解决方法是遍历数组，找出target最后出现的位置即可。时间复杂度是O(n)。
考虑使用二分法：用l指向区间的左端点，r指向区间的右端点，取mid = (l + r) / 2，mid 指向区间中间位置。
左右端点更细规则如下：
如果a[mid] > target，target最后一次出现的位置一定在a[mid]之前，更新r：r = mid - 1。
如果a[mid] <= target，target最后一次出现的位置可能在mid处，也可能在a[mid]之后，更新l：l = mid。
直到 l = r时，区间内只有一个元素，这个元素就是target最后一次出现的位置。
看起来很正确的方法，手动模拟下：
第一次：l = 0, r = 4, mid = (l + r) / 2 = 2。a[mid] = 3。符合更新规则2，l更新为mid：l = 2。
第二次：l = 2, r = 4, mid = (l + r) / 2 = 3。a[mid] = 3。符和更新规则2，l更新为mid：l = 3。
第三次：l = 3, r = 4, mid = (l + r) / 2 = 3。a[mid] = 3。符合更新规则2，l更新为mid：l = 3。
第四次：l = 3, r = 4, mid = (l + r) / 2 = 3。a[mid] = 3。符合更新规则2，l更新为mid：l = 3。
我们发现，从第三次开始陷入了死循环。
来看看为什么出现了这种情况
在第三次处理过程中，l = 3, r = 4。mid = (l + r) / 2 = 3。a[mid] = 3。l更新为mid：l = 3。
可以发现，l更新前的值为3，更新后，l的值为还为3。更新前后l的值没变，因此陷入了死循环。
原因在于：通过(l + r) / 2 计算mid的值，结果是向下取整的。在区间内只有两个元素的时，r的值可以用l + 1代替，因此mid = (l + r) / 2 = (l + l + 1) / 2 = l。这个时候更新l = mid，l的值更新后依旧为l。 下次处理的区间和这次相同，陷入了死循环。
所以说：如果程序中出现了l = mid，因为整数除法结果是向下取整，所以l更新后的值可能等于更新前值，因此陷入死循环。
如何解决l = mid 陷入死循环的问题
想办法让l每次更新后的值都大于l，区间就能不断缩小，就不会陷入死循环。
具体的：让mid的取值为(l + r) / 2向上取整，这样l更新为mid后，l更新后的值一定会大于更新前的值。
(l + r) / 2向上取整的值如何得到？
如果l + r为奇数，(l + r) / 2向上取整等于(l + r + 1) / 2向下取整；如果l + r为偶数，(l + r) / 2向上取整也等于(l + r + 1) / 2向下取整。
因此，只要程序中有l = mid这种情况，mid就用mid = (l + r + 1) / 2计算即可。
等等，这样会出引入一个新的问题
mid的值通过(l + r + 1) / 2 计算。在区间内只有两个元素的时，l的值可以用r - 1代替。因此mid = (l + r) / 2 = (r - 1 + r + 1) / 2 = r。如果程序用r = mid更新右边界，更新后r = r，区间不变，陷入死循环。所以，当程序中r的更新为r = mid 时，mid的值计算不能用 (l + r + 1) / 2。
总结：
mid 用(l + r) / 2计算时，如果程序中有l = mid ,程序会陷入死循环。
mid 用(l + r + 1) / 2计算时，如果程序中有r = mid ,程序会陷入死循环。
如何优雅的解决左右端点更新的问题？
程序中不要同时出现l = mid, r = mid这两条语句。
如过程序中出现了l = mid，mid的值用 (l + r + 1) / 2计算。
如果程序中出现了r = mid，mid的值用（(l + r) / 2计算。
2. 何时停止二分
每次二分，通过更新l或r不断缩小区间，并保证答案一定在区间内。当区间内只有一个元素时，判断这个元素是否为答案，完成算法。
优雅的停止二分：
当l<r成立时，进行二分。l = r时停止。停止后进行判断，是答案输出，不是答案，此题无解。
进阶：
分巧克力
儿童节那天有 K 位小朋友到小明家做客。
小明拿出了珍藏的巧克力招待小朋友们。
小明一共有 N 块巧克力，其中第 i 块是Hi×Wi 的方格组成的长方形。
为了公平起见，小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。
切出的巧克力需要满足：
- 形状是正方形，边长是整数
- 大小相同
例如一块 6×5的巧克力可以切出 6 块2×2 的巧克力或者 2 块 3×3 的巧克力。
当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？
输入格式
第一行包含两个整数 N 和 K。
以下 NN 行每行包含两个整数Hi 和 Wi。
输入保证每位小朋友至少能获得一块 1×1 的巧克力。
输出格式
输出切出的正方形巧克力最大可能的边长。
数据范围
1≤N,K≤105
1≤Hi,Wi≤105
输入样例：
2 10
6 5
5 6
输出样例：
2代码：
#include <iostream>
using namespace std;
int const N = 100010;
int w[N], h[N];//存储长、宽
int n, k;
bool chack(int a)
{
int num = 0;//记录分成长度为 a 的巧克力数量
for (int i = 0; i < n; i++)
{
num += (w[i] / a) * (h[i] / a);//每一大块可以分成的边长为 a 的巧克力数量
if (num >= k) return true;//大于要求数量，返回真
}
return false;
}
int main()
{
cin >> n >> k;
for (int i = 0; i < n; i++) cin >> h[i] >> w[i];
int l = 1, r = 1e5;//小巧克力数量边长一定在 1 -- 100000 之间
while (l < r)//二分小巧克力边长范围，找到符合要求的最大值
{
int mid = l + (r - l + 1 >> 1);//因为l = mid ，所以 mid 取 l + r + 1 >> 1,为了防止加和越界，改写成 l + (r - l + 1 >> 1)
if (chack(mid)) l = mid;
else r = mid - 1;
}
cout << r;
}