二分算法归纳

算法模板

二分模板一共有两个，分别适用于不同情况。
算法思路：假设目标值在闭区间[l, r]中， 每次将区间长度缩小一半，当l = r时，我们就找到了目标值。

版本1

当我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时，其更新操作是r = mid或者l = mid + 1;，计算mid时不需要加1。 该模板为最大值最小化 或者为从小往大找

C++ 代码模板：

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

版本2

当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时，其更新操作是r = mid - 1或者l = mid;，此时为了防止死循环，计算mid时需要加1。该模板最小值最大化 或者为从大往小找

C++ 代码模板：

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

check函数

每次二分数值的时候，我们都需要一个check函数去判断当前需要更新的范围，并且需要注意能否取到边界，具体题目的逻辑具体看。这是需要经验累积的。来自一个题解下提供的思路。

算法理解

对于二分的算法的理解，我给自己引入了一个最基础的例子作为引子，可以延伸到后面，二分的实质实际上每次就答案的区间一分为二，一部分是符合条件的值，之后是不符合条件的值。
比方说给定一个tagget，在1到100之间，那么每次我们吧区间一分为二，都可以得出两个区间，一个比target大的区间，一个是比target小的区间，那么通过check函数比对便可以不断缩小边界。直到l和r相等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>  
using namespace  std;
//给定区间 1-100 目标数为56 在一定次数内猜出来


int main()
{  

    int num[10]={1,22,33,44,56,66,77,88,99,100};
    int target=56;
    int l=0;
    int r=9;
    while(l<r)
    { int mid=l+r+1>>1;
      if(num[mid]<=target) l=mid;
      else r=mid-1;
       


    }

  cout<<num[l]<<" "<<num[r];
    
}

算法例题