模板1

  • 当我们将区间 [l, r] 划分为 [l, mid] 和 [mid + 1, r] 时，其更新操作是 r = mid 或者 l = mid + 1，计算 mid 时不需要加1，即 mid = (l + r) / 2;

    1. int bsearch_1(int l, int r)
    2. {
    3.   while (l < r)
    4.   {
    5.       int mid = (l + r)/2;
    6.       if (check(mid)) r = mid;
    7.       else l = mid + 1;
    8.   }
    9.   return l;
    10. }

    模板2

  • 当我们将区间 [l, r] 划分为 [l, mid - 1] 和 [mid, r] 时，其更新操作是 r = mid - 1 或者 l = mid，计算 mid 时需要加1，即 mid = (l + r + 1) / 2;

    1. int bsearch_2(int l, int r)
    2. {
    3.   while (l < r)
    4.   {
    5.       int mid = ( l + r + 1 ) /2;
    6.       if (check(mid)) l = mid;
    7.       else r = mid - 1;
    8.   }
    9.   return l;
    10. }

    使用选择

  • 二分缩小区间时观察左边界的更新情况来选择模板

  • 循环结束优先取 r