本文正在参加「金石方案」

二分查找背模板？我选择去了解它！：浮点篇

零、序文

在之前的根底篇里，咱们讲过了最常用的两种二分查找：（没有看过的能够点进主页看看根底篇）

• 找出数组中第一个大于等于x的数的方位；
• 找出数组中最终一个小于等于x的数的方位；

一般来说，需求运用二分的状况也根本便是这两种了，二分查找类题也差不多都是由这两个模板伸延而来。

但二分查找除此之外还有一种更特别的用法，尽管用的当地不多，可是学了也没差嘛。

知识总不会害人的，而且指不定什么时分它就帮了你大忙呢？

今日咱们的文章要提到的它便是——

一、浮点型二分

浮点型，通俗易懂的来说便是咱们常见的小数，整数在计算机中被称为整型，小数就被称为浮点型。

咱们之前根底篇学过的两种模板，都是整型二分，你看，不论是区间长度，仍是枚举的下标，他都是整数。

而浮点二分就很奇特了：它的区间端点是带有小数，枚举的方位mid也是带有小数。

此时你或许会觉得古怪：

”枚举的方位mid带有小数？数组的下标不是只能对错负整数吗？居然还能用小数去指向数组吗？“

那答案当然是！——不能。

数组的下标的的确确只能对错负整数，可是！——我什么时分说，浮点型二分是用在数组上面了？

是的！浮点型二分并不是用于在数组中查找什么东西，在数组中查找东西用根底篇那两个就够够的了，咱们浮点型二分可是要干奇特的事！

老规矩，举个栗子：

我给你一个整数x，让你输出它的平方根 x\sqrt{x}x​ ，保存4位小数。

这个对咱们大部分同学来说应该是比较简略的，由于大部分同学都知道咱们有一个 $sqrt(intx)$ 函数，它能够直接帮咱们把一个数 $x$ 的平方根算出来。咱们只要在输出的时分只保存四位小数就行了，很简略呀。

难度升级：

我给你一个整数x，让你输出它的立方根 x3\sqrt[3]{x}3x​ ，保存4位小数。

再来：

我给你一个整数x，让你输出它的7次方根 x7\sqrt[7]{x}7x​ ，保存4位小数。

再来！

我给你两个整数x和n，让你输出x的n次方根 xn\sqrt[n]{x}nx​ ，保存4位小数。

现在呢？现在你还能用sqrt()函数偷懒吗？

咱们知道，二分查找的进程便是每次枚举区间的中心方位，然后依据该方位和正确答案的联系来不断地缩短左区间or右区间，最终找到正确答案的方位。

咱们举的算n次方根的比如，其实也能够看作是在区间查找答案。

拿算x的立方根为比如，假如x的大小范围是 $0$ 到 10510^5105 ，那么咱们能够给区间的左端点 $l$ 设为0，右端点 $r$ 设为10^5（实际上100左右就够了）。

然后每次咱们枚举中心的方位 $mid$ 那么当前mid和答案的联系便是，假如 $mid\ast mid\ast mid$ 的值大于x，就阐明咱们枚举的立方根过大了，右区间缩短；反之假如小于x，就阐明枚举的立方根过小，左区间缩短。

重复这一进程，假如x有一个整数的立方根（比如8的立方根是2），那咱们就一定能够依据这个办法，求出这个立方根。

可是要注意，这里有一个很重要的条件：假如x有一个整数的立方根。

是的，假如x没有整数的立方根，咱们又怎么能够通过枚举整数来取得这么一个结果呢？

而事实上，具有整数立方根的数其实不算多，占大头的仍是那些没有整数立方根的数，关于它们，咱们再去用整型二分显然是不可的。

这时分就要浮点型二分出手了！它是怎么做到的呢？

让咱们来看看——

二、好古怪又好简略的完成进程

咱们先看一下根底篇的整型写法：

//查找数组中第一个大于x的元素
while(l<r)
{
  int mid=(l+r)/2;
  if(a[mid]<x)l=mid+1;
  else r=mid;
}
​
//查找数组中最终一个小于等于x的元素
while(l<r)
{
  int mid=(l+r+1)/2;
  if(a[mid]<=x)l=mid;
  else r=mid-1;
}

再看看浮点二分的写法：

double l=0,r=100000;
while(r-l>1e-5)
{
   double mid=(l+r)/2;
   if(mid*mid*mid>=x)r=mid;
   else l=mid;
}

通过比较，不难看出浮点二分和整型二分有3个比较明显的区别：

1. $l$ 、 $r$ 、 $mid$ 的数据类型不再是int而是改为了double；
2. 循环持续的条件从 $l<r$ 改为了 $r-l$ 大于一个很小的小数；
3. 缩短区间时， $l$ 、 $r$ 和 $mid$ 不再有+1或-1操作；

咱们一步步来解说：

$l$ 、 $r$ 、 $mid$ 的数据类型改为了double，这便是它被称之为浮点二分的原因：咱们的区间端点以及枚举的方位都是浮点数，比较好了解。

为什么不必+1-1了呢？

能够想到，浮点二分区间缩短到后边时，整数部分根本现已确定下来了，只是在寻觅精确的小数部分，假如咱们在缩短的时分将端点+1-1，会修正整数的部分，那有或许直接将答案略过。所以咱们不对枚举的方位和区间端点进行+1-1操作。

这也旁边面阐明了浮点二分没有边界问题，所以能够说它其实比整型二分还简略些。

至于循环完毕条件，由于区间端点不再进行+1-1操作，也便是说 $l$ 和 $r$ 只能无限挨近，尽管最终能够呈现l==r的状况，可是这也需求循环一定的次数，太麻烦了。

所以咱们想，当 $l$ 和 $r$ 现已满意挨近的时分，就完毕循环，至于这个“满意挨近”就和标题要求的精度有关了。

比如在咱们之前求根问题时，就说过： “保存4位小数” 。

这个 “四位小数” 便是咱们的精度。

假如要求一个肯定精确的答案，那咱们就需求循环很屡次，把两个端点的所有小数都保持持平。

但假如只要保存4位小数，那么咱们只需求两个端点的前4位小数持平就行，后边的n多个小数位咱们都不需求处理了。

至于保证两个端点的前4位小数持平，那右端点 $r$ 减去 $l$ 的小于0.00001时就能够，此时答案就满意标题的要求了。

所以咱们的循环持续条件为： $r-l>精度$ ；

一道题的精度一般会在标题说出，假如没说，咱们一般默许是1e-6，即10^{-6}。

弥补一下，除了使用while循环配合精度来进行浮点二分时，还有一种使用for循环的奇特的写法：

double l=0,r=100000;
for(int i=1;i<=500;i++)
{
   double mid=(l+r)/2;
   if(mid*mid*mid>=x)r=mid;
   else l=mid;
}

这样便是不管精度多少，固定循环500次后就完毕二分。实际循环500次的精度就现已满意了，再写题时也能够适当的添加或减少循环次数。

至此，浮点二分的原理和完成咱们都讲完了。

仍是那句话，掌握一个知识点不是看看网课看看文章就能叫会了，而是通过写题堆集经验，把这个知识点玩出花来。

趁热打铁，咱们——

三、苏醒了，猎题时间

790. 数的三次方根 – AcWing题库

问题解析

这题便是要咱们求n的三次方根，n的范围是-10000到10000，那么l的初始值能够设为-100，r的初始值能够设为100，然后在之中寻觅n的三次方根。要注意的是标题要求咱们输出6位小数，那么就需求把精度设为1e-7。

AC代码

#include<iostream>
using namespace std;
int main()
{
   double x;
   scanf("%lf",&x);
   double l=-100,r=100, mid;
   while(r-l>1e-7)
   {
     mid=(l+r)/2;
     if(mid*mid*mid>=x)r=mid;
     else l=mid;
   }
   printf("%lf",l);
   return 0;
}

第十四届蓝桥杯C++B组：B、01串的熵

问题描述

问题解析

答案：11027421

这题对我来说主要难点在于算log，说实话我之前真不知道有函数能直接算log，这题的log我是采用了浮点型二分的办法来算的。（所以说，多学一个知识总是好的，关键时分能救命呀）

并且也测试了下S=100的状况发现是正确的。然后咱们就枚举0的个数就好了，1的个数便是23333333-0的个数。

不过我这做法有两点要注意的：

1. 没必要从0开端枚举0的个数，实际上debug几遍后就能发现大约在11000000左右的时分算出来的值就很挨近标题的这个值了。
2. 二分的精度要高，一开端我习惯性的设置精度为1e-6，结果咋都跑不出正确结果，后来折磨了半小时后才发现精度要开到1e-15左右才能出正确结果。哭死。

AC代码

#include<iostream>
using namespace std;
#include<cstdio>
#include<algorithm>
#include<string>
#include<unordered_map>
#include<queue>
#include<vector>
#include<stack>
#include<map>
#include<string.h>
#include<math.h>
#include<iomanip>
​
​
#define int long long
#define endl '\n'
typedef long long ll;
typedef pair<ll,ll> PII;
const int N=1e5+10;
​
​
//算log2(a)的值(我不会用函数啥的算，也不知道有没有现成的函数，但我知道有现成的幂运算） 
double check(double a)
{
    double l=-10,r=0;
    //精度开小了会寄掉，一开端我写的1e-6,咋都不出结果 
   while(abs(r-l)>=1e-15)
    {
       double mid=(l+r)/2;
        if(pow(2,mid)>a)r=mid;
        else l=mid; 
    }
    return l;       
} 
​
//答案:11027421
​
void solve()
{
    //double x=check(1.0/3),y=check(2.0/3);
    //测试后,答案等于1.3083,阐明办法没问题 
    //cout<<fixed<<setprecision(5)<<-1.0/3*x+-2.0/3*y-2.0/3*y;
    //没必要从0开端枚举，算的太慢了 
    for(int i=11026000;i<=23333333/2;i++)
    {
        if(i>=23333333-i)continue;
        double a=i/23333333.0,b=(23333333-i)/23333333.0;
        double x=check(a),y=check(b);
        double z=i*(-1.0*i/23333333.0*x)+(23333333-i)*(-1.0*(23333333-i)/23333333.0*y);
​
        if(abs(11625907.5798-z)<=1e-4)
        {
            cout<<i<<endl;
            return;
        }
​
    }
}
​
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}

四、结束

由于没有边界条件，所以浮点二分的模板并不难记。

整型二分之前都是在数组中寻觅答案，而浮点二分比起 “寻觅答案” ，更像是 “枚举答案” 。

本片文章在介绍浮点二分这一特别的二分查找模板外，也是想让大家提前体验一下 “枚举答案” 的思维和巧妙之处。

这也是二分中，另一个很重要的用法——二分答案。，这也是咱们下次文章即将讲到的一种奇特的算法。

最终假如本篇文章帮到了您，不知是否能点一个小小的赞呢。（拜托了！这对我真的很重要！）