整数二分模板

 1 bool check(int x) {/* ... */} // 检查x是否满足某种性质
 2 
 3 // 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
 4 int bsearch_1(int l, int r)
 5 {
 6     while (l < r)
 7     {
 8         int mid = l + r >> 1;
 9         if (check(mid)) r = mid;    // check()判断mid是否满足性质
10         else l = mid + 1;
11     }
12     return l;
13 }
14 // 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
15 int bsearch_2(int l, int r)
16 {
17     while (l < r)
18     {
19         int mid = l + r + 1 >> 1;
20         if (check(mid)) l = mid;
21         else r = mid - 1;
22     }
23     return l;
24 }