学习内容

    二分是一种经典的算法思想。利用排除法的思想，可以把线性时间复杂度O(n)的问题优化到O(logn)。不仅能对有序序列进行二分查找。只要在某个边界，左或右满足某种性质，二分就可以找到这个边界。

    整数二分的模板

    1. bool check(int x) {/* ... */} // 检查x是否满足某种性质
    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. }

    第 08 天课程题目：

    第 09 天课程题目：

    第 10 天课程题目：