二分答案的味道

有一类题目是在"猜答案"：先猜一个值，检验它行不行，如果行就往一个方向继续猜，不行就往另一个方向。因为"答案越大越容易满足（或越难满足）"这种单调关系存在，猜的过程也能二分，只不过找的不是数组里的元素，而是一个临界值。猜数字游戏就是这个味道。

#include <iostream>
using namespace std;
// 求 x*x <= 36 的最大整数 x（即 36 的整数平方根）
int main() {
    int lo = 0, hi = 36, ans = 0;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (mid * mid <= 36) { ans = mid; lo = mid + 1; }  // 行，试更大
        else hi = mid - 1;                                 // 不行，往小
    }
    cout << ans;                            // 6
}

用二分答案的前提，还是那个单调性：必须保证"猜大了一直行、猜小了一直不行"（或反过来），否则不能这么砍。