y总总结的模板：y总yyds

二分查找的算法思路

假设目标值在 闭区间[l,r]中，每次将区间长度缩小一半，选择包含目标值的区间继续二分，当l==r，就找到了目标值。

整数二分问题解题步骤

1. 先写出mid的表达式（先不加1），写出判断条件或者判断函数check
2. 分析如何更新区间
3. 若 l = mid，则“要+1”，l + r + 1 >> 1；若r = mid，则不用+1，l + r >> 1

模板1

当把区间划分成[l,mid] 和[mid + 1, r]，即更新操作是r = mid，l = mid + 1，此时计算mid不用+1

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,mid - 1] 和[mid, r]，即更新操作是r = mid - 1，l = mid，此时计算mid需要+1

  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;
}

这两个模板可以包含所有整数二分问题。

例题：原题链接

//因为是升序排列的数组，所以我们可以用二分查找
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N];
int main()
{
    int n,q;
    scanf("%d%d",&n,&q);
    for(int i = 0;i<n;i++) scanf("%d",&a[i]);
    while(q--)
    {
        int k;
        scanf("%d",&k);
        int l = 0;
        int r = n;
        while(l<r)  //该二分查找是查找k的初始位置
        {
            int mid = l + r >> 1;   //因为下面是r = mid，所以不用+1
            if(a[mid]>=k)  //"性质"
            {
                r = mid;  //a[mid]可能是目标答案，故是r=mid而不是mid-1.
            }
            else
            {
                l = mid + 1;  //若上面是r = mid，else就肯定是l = mid + 1
            }
        }
        if(a[l]!=k)  //当l==r，退出循环。判断序列中是否有k这个数
        {
            cout<<"-1 -1"<<endl;
        }
        else   //输入的数组里至少有一个数等于k
        {
            cout<<l<<' ';    //此时l==r，输出r也是一样的

            int l = 0;   //一定要记得重新初始化l和r
            int r = n-1;
            while(l<r)    //继续进行查找k的终止位置的二分查找
            {
                int mid = l + r +1 >> 1;   //因为下面是l=mid，所以要加一
                if(a[mid]<=k)
                {
                    l = mid;  //此时mid可能是答案，所以不是mid+1
                }
                else
                {
                    r = mid - 1; 
                }
            }
            cout<<l<<endl;
        }
    }
    return 0;
}

浮点数二分

浮点数二分就非常简单了，不用考虑边界问题，很随意

例题1：输入x求根号x

//浮点数二分就不会有各种边界问题，不用考虑+1什么的

#include <bits/stdc++.h>
using namespace std;

int main()
{
    double x;
    cin>>x;
    double l = 0,r = max(1,x); //r不能小于1，因为如果x是0.01，则答案0.1不在[0，0.01]内
    while(r-l>1e-8)
    {
        double mid = (l+r)/2;
        if(mid*mid>x)  //说明答案在l到mid
        {
           r = mid; 
        }
        else
        {
            l = mid;   //完全不用考虑什么加一减一
        }
    }
    cout<<l<<endl;
    return 0;
}

例题2 求x的三次方根

原题链接

// 这题不能让l= 0，r = n。因为比如n = 0.001,他的答案其实是0.1，那你把l= 0，r=0.001，答案都不在这里面
//所以索性让l = -10000，r = 10000，n的三次方根总在这个范围内

//浮点数的二分，“易过借火”，很随意

#include <bits/stdc++.h>
using namespace std;
int main()
{
    double n;
    cin>>n;
    double l = -10000;
    double r = 10000;
    while(r-l>1e-8)   //因为要保留6位小数，根据经验，这里一般多2位，即1e-8
    {
        double mid = (l+r) / 2;  //浮点数不能用位运算，也不用考虑+1
        if(mid*mid*mid > n)  //答案在mid左边
        {
            r = mid;
        }
        else
        {
            l = mid;
        }
    }
    printf("%.6lf",l);
    return 0;
}