二分的模板（新手上路）

今天开始来复习算法基础课的内容了 今天是二分 二分有好几种类型 ，

先上板子（数列默认升序，如果没有升序可以用sort排一下）；

事先给初学者一个口诀：先判右即大于等于，先判左即小于等于；

1 求升序序列的数组中小于等于某个数（target）的最小值

​
int str[100]; //假设已经排好序的给定数组；
int l = 0 , r =  n - 1;
while(l < r)
{
   int mid = l +r >> 1;  //这里是移位运算；二进制向右移动一位，相当于除以二;
   if(str[mid] >= target(要查找的那个数) )r = mid;
   else l =  mid+1; 这里的 l = mid + 1 是为了区间的不重不漏原则；
}
 cout << str[l]< 
再上第二个板子
 找出升序序列的大于等于某个数的最大值；
 
int  str[100];
int l = 0 , r = n - 1;
while(l < r)
{
   int mid = (l + r +1) >> 1;//这里加上1是防止陷入死循环；
   if(str[mid] <= targe) l = mid;
   else r = mid - 1;
}
 cout << str[l] << endl;
 
注意 在例子中我并没有判断是否这个条件不成立的情况，如果要加上可以在最后的 cout 前加上一个判断语句即可 ，接下里我们来探讨。
 
本质核心内容以及核心思想其实只有几行代码，而这几行代码中对区间的判定可以决定搜索的条件，如
 ：找到给定数列中大于等于某个数的最小值，这时候（默认升序）你在二分的过程中需要对更新左边界与右边界的条件进行一个思考 ， 反过来，如果我们要找到该序列中小于等于某个数的值，这时候同样要进行对边界条件的系修改 ， 如下面这道题
 
 这是在acwing上一道经典的题目；在这个题目中我们可以看到，这个其实就是对两个板子的应用；
 下面就是ac代码
 
#include
#include

using namespace std ;
const int N = 100010;

int a[N];

int main()
{
    int n , q;
    cin >> n >>q;
    for(int i = 0 ; i < n ; i++)cin >> a[i];

    while(q--)
    {
        int l = 0 , r = n-1;
        int o ;
        cin >>o ;

        while(l >1;
            if( a[mid] >= o)r = mid;
            else l = mid+1;
        }

        int kk = l ;

        l = 0 , r=  n-1;

        while( l < r)
        {
            int mid = (l+r+1)/2;
            if(a[mid] <= o)l = mid;
            else r = mid-1;
        }
        if(a[kk] == o && a[r] ==o)
        {
            cout << kk <<' '<< r < 
整来说 ，对初学者来说判断边界有时候会早不到头脑，便一直出错；其实其原理大家并不需要理解的太过于深刻，因为解决实际问题的时候我们需要的是写出来这个算法来解决问题，并不是要去写这个算法的证明，
 
另外 ，要注意一下二分的开始的 l 与r 的范围， 尽量接近已知符合要去的范围，范围越小运行的越快。
 学习算法的小伙伴们咱们一起加油吧！