3 二分算法查找

//二分有整数二分和浮点数二分
//二者有不同的模板
//首先来看看整数的二分
//当找的是区间右边界，用mode1
int mode1(int l,int r)//模板1区间[l,r]被划分为[l,mid]和[mid+1,r]使用
{  //当然下面的循环也可以改成循环100次，2的100次方足够大，让我们找出答案
    while(l>1;//开始二分
        if(judge(mid)) r=mid;//judge是自己定义的函数，假如judge出来的数大于期望的，说明期望的数在右边，则得缩小范围
        else l=mid+1;//否则在期望的数在左边，继续缩小
        //这里说明一下 假如r=mid，则l一定得为mid+1,目的防止越界
    return l;//返回期望值
}
//当找的是区间左边界，用mode2
int mode2(int l,int r)//模板2区间[l,r]被划分为[l,mid-1]和[mid,r]使用
{   //当然下面的循环也可以改成循环100次，2的100次方足够大，让我们找出答案
    while(l>1;//开始二分，l+r+1不能写成l+r，不然会死循环
        if(judge(mid)) l=mid;//judge是自己定义的函数，假如judge出来的数小于期望的，说明期望的数在左边边，则得缩小范围
        else r=mid-1;//否则在期望的数在右边，继续缩小
        //这里说明一下 假如l=mid，则r一定得为mid-1,目的防止越界
    }
    return l;//返回期望值
}
//再看看浮点数二分
//浮点数就没那么多讲究了
double mode(double l,double r)
{   //当然下面的循环也可以改成循环100次，2的100次方足够大，让我们找出答案
    while(r-l>1e-8)//看题目要求精确到几位小数，加入两位，则是1e-4，都比要求要多2
    {
        double mid=l+r>>1;//开始二分
        if(judge(mid)) r=mid;//judge是自己定义的函数，假如judge出来的数大于期望的，说明期望的数在右边，则得缩小范围
        else l=mid;//否则在期望的数在左边，继续缩小
        //这里不用考虑+1或者-1的情况，因为浮点型除法是准确的
    }
    return l;//返回期望值
}

789. 数的范围 - AcWing题库https://www.acwing.com/problem/content/791/

下面来看列子 

#include
using namespace std;
const int N=1e6+10;
int a[N];
int main()
{     int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0;i>1;
           if(a[mid]>=x) r=mid;
           else l=mid+1;
       }
       if(a[l]!=x) printf("-1 -1n");
       else
       {
           printf("%d ",l);//输出左边界
            l=0,r=n-1;
           while(l>1;
               if(a[mid]<=x) l=mid;
               else r=mid-1;
           }
            printf("%dn",l);//输出右边界
       }
   }
        return 0;
}

790. 数的三次方根 - AcWing题库https://www.acwing.com/problem/content/792/下面给出浮点代码

#include
using namespace std;
int main()
{     double n;
    scanf("%lf",&n);
  double l=-10000,r=10000;
  while(r-l>1e-8)//题目要求精确到6位小数则这里条件则得写6+2=8位
  {
      double mid=(l+r)/2;
      if(mid*mid*mid>n) r=mid;//mid*mid*mid>n是judge条件
      else l=mid;
  }
  printf("%.6lfn",l);
        return 0;
}