知识来源

来源：AcWing——算法基础课
链接：https://www.acwing.com/activity/content/introduction/11/

整数二分查找

1. 适用范围

• 存在某种性质p，可以将整个区间分成两部分，一部分满足性质p，另一部分不满足，则二分可以找出其边界点

• 如图1所示两个边界点均可以通过二分查找找出来；

2. 算法步骤

• 以找左半部分的边界点为例，如图2为我们要寻找的目标边界点

• Step 1：取得中间点mid = (L + R) / 2

• Step 2：观察点mid所处的区间，是红色区间还是绿色区间

  • 若mid所处区间是红色区间，如图2-1所示，则mid有可能取到我们要求的目标边界点

  

  • 若mid所处区间是绿色区间，如图2-2所示，则mid不可能为我们要求的边界点

  

• Step 3：更新查询区间[L，R]

  • 若mid所处区间是红色区间，由于mid有可能取到我们要求的目标边界点，则更新后的区间需要保留mid，因此更新区间为[mid, R]，即：L = mid
  • 若mid所处区间是绿色区间，由于mid不可能取到我们要求的目标边界点，则更新后的区间不需要保留mid，因此更新区间为[L, mid - 1]，即：R = mid - 1

• 重复上述步骤直到 L = R

• 寻找右半部分边界点的过程与上述过程高度相似，不再赘述，读者可以自行推导

3. 算法模板

//查找左边界点
while(l < r)
{
    int mid = l + r + 1 >> 1;  //注意更新区间时若为l = mid，此处需要+1，避免死循环
    if(checkRed(mid)) l = mid;
    else r = mid - 1;
}

//查找右边界点
while(l < r)
{
    int mid = l + r >> 1;
    if(checkGreen(mid)) r = mid;
    else l = mid + 1;
}