二分算法的解题过程及总共四种情况的讨论

文章目录

• 二分算法的解题过程及总共四种情况的讨论
• • 解题步骤
  • 四种情况讨论
  • 代码模板

解题步骤

1. 确定二分性质

2. 确定分界点

3. 确定更新区间

4. 确定取整方向

   小技巧: mid, l 和 r 的赋值语句有且只有一个 + 1

例:
从 0 1 2 3 4 5 中返回 3 的下标 3
1.二分性质 
    根据是否 >= 3 将整个数组分为 0 1 2 和 3 4 5, 左分界点为 2, 右分界点为 3
2.分界点
    寻找的结果是右分界点 3
3.确定更新区间
    原区间为 [l, r], 暂定 mid = (l + r) / 2
    当 mid 满足二分性质时, 即 mid 在 3 4 5 这一侧时, 更新区间为 [l, mid]
    当 mid 不满足二分性质时, 即 mid 在 0 1 2 这一侧时, 更新区间为 [mid + 1, r]
4.确定取整方向
    小技巧: 有且只有一个 + 1
    小技巧的含义是: 在 mid 和 l 和 r 的赋值语句中有且只有一个 + 1
    由于更新区间中有一个 + 1, 即 l = mid + 1, 所以 mid = (l + r) / 2 没有 + 1

四种情况讨论

case 1

>= 3 右分界点

1. 二分性质为 >= 3

   check(x)
       if x >= 3
           return true
       else
           return false
   

2. 寻找右分界点

   右分界点 3

3. 更新区间

   暂定 mid = (l + r) / 2
   if check(mid)
       新区间为 [l, mid]
       更新 r = mid
   else
       新区间为 [mid + 1, r]
       更新 l = mid + 1
   

4. 取整方向

   由于 l = mid + 1 中有一个 + 1

   所以 mid 不需要 +1, 最终 mid = (l + r) / 2

case 2

>= 3 左分界点

1. 二分性质为 >= 3

   check(x)
       if x >= 3
           return true
       else
           return false
   

2. 寻找左分界点

   左分界点 2

3. 更新区间

   暂定 mid = (l + r) / 2
   if check(mid)
       新区间为 [l, mid - 1]
       更新 r = mid - 1
   else
       新区间为 [mid, r]
       更新 l = mid
   

4. 取整方向

   由于r = mid - 1和 l = mid 中没有 + 1

   所以 mid 需要 +1, 最终 mid = (l + r) / 2 + 1

case 3

< 3 右分界点

1. 二分性质为 < 3

   check(x)
       if x < 3
           return true
       else
           return false
   

2. 寻找右分界点

   右分界点 3

3. 更新区间

   暂定 mid = (l + r) / 2
   if check(mid)
       新区间为 [mid + 1, r]
       更新 l = mid + 1
   
   else
       新区间为 [l, mid]
       更新 r = mid
   

4. 取整方向

   由于 l = mid + 1 中有一个 + 1

   所以 mid 不需要 +1, 最终 mid = (l + r) / 2

case 4

< 3 左分界点

1. 二分性质为 < 3

   check(x)
       if x < 3
           return true
       else
           return false
   

2. 寻找左分界点

   左分界点 2

3. 更新区间

   暂定 mid = (l + r) / 2
   if check(mid)
       新区间为 [mid, r]
       更新 l = mid
   else
       新区间为 [l, mid - 1]
       更新 r = mid - 1
   

4. 取整方向

   由于r = mid - 1和 l = mid 中没有 + 1

   所以 mid 需要 +1, 最终 mid = (l + r) / 2 + 1

代码模板

case 1

>= x 右分界点

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;		//这三行代码有且只有一个 + 1
        if (check(mid)) r = mid;    // check()判断mid是否满足二分性质
        else l = mid + 1;
    }
    return l;
}

case 4

<= x 左分界点

// 区间[l, r]被划分成[l, mid - 1]和[mid, r]
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;	//这三行代码有且只有一个 + 1
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}