#include<bits/stdc++.h>
using namespace std;
int j;
double a,b,c,d,m;
double fc(double x)
{
    return a*x*x*x+b*x*x+c*x+d;
}
int main()
{
    cin>>a>>b>>c>>d;
    for(double i=-100;i<=100;i++)
    {
        double l=i;
        double r=i+1;
        if(!fc(l))
        {
            printf("%.2lf ",l);
        }
        if(fc(l)*fc(r)<0)
        {
            while(r-l>=0.001)
            {
                m=(l+r)/2;
                if(fc(l)*fc(m)<=0)
                {
                    r=m;
                }
                else if(fc(l)*fc(m)>0)
                {
                    l=m;
                }
            }
            printf("%.2lf ",r);
            j++;
        }
        if(j==3)
        {
            break;
        }
    }
    return 0;
}

第一题思路非常明显

在区间内，每次加1，根据性质若出现<0的，则对长度为1的区间进行二分。

 

二分的基础用法是在单调序列或单调函数中进行查找。

使用条件：单调性

复杂度：判定小于求解

 

整数域上：

1.终止边界

2.左右区间取舍时的开闭情况

 

实数域：

1.精度

 

整数集合上的二分

最终答案处于[l,r]以内，循环以l==r结束，每次二分中间值mid会归属于左半段或右半段二者之一

 

在单调递增序列a中查找大于等于x的数中最小的一个

while(l<r)
    {
        int mid=(l+r)/2;
        if(a[mid]>=x)
        {
            r=mid;
        }
        else
        {
            l=mid+1;
        }
    }    
    return a[l];

 

在单调递增序列a中查找小于等于x的数中最大的一个

while(l<r)
    {
        int mid=(l+r+1)/2;
        if(a[mid]<=x)
        {
            l=mid;
        }
        else
        {
            r=mid-1;
        }
    }
    return a[l];

注意到mid有两种写法1

1.

int mid=(l+r)/2;
        if(a[mid]>=x)
        {
            r=mid;
        }
        else
        {
            l=mid+1;
        }

2.

int mid=(l+r+1)/2;
        if(a[mid]<=x)
        {
            l=mid;
        }
        else
        {
            r=mid-1;
        }

认真观察可知，二分核心是减小观察区间。

对于第二段，若mid取l+r，极限情况r只比l大1的情况下，

若a[mid]<=x，mid==l，则区间并未缩小，进入死循环。

若走else，r<l，循环不能以r==l结束

 

分析还可知，mid=(l+r)/2取不到r，mid=(l+r+1)/2取不到l。

 

处理无解的情况，把最初的二分区间[1,n]扩大到[1,n+1]或[0,n]，把a数组一个越界的下标包含进来。

若二分终止于越界下标上，则说明a中不存在所求的数。

 

实数域上的二分

确定需要的精度eps，l+eps<r为循环条件,一般需要保留k位小数的时候，取eps=10^-（k+2）

while(l+1e-5<r)
    {
        double mid=(l+r)/2;
        if(calc(mid))
        {
            r=mid;
        }
        else
        {
            l=mid;
        }
    }

 

若需要更高精度，可以固定循环次数的二分方法

for(int i=0;i<100;i++)
    {
        double mid=(l+r)/2;
        if(calc(mid))
        {
            r=mid;
        }
        else
        {
            l=mid;
        }
    }

 

拓展：

三分求单峰函数极值

单峰函数：

拥有唯一的极大值点，极大值左侧严格单调上升，右侧严格单调下降

单谷函数：

或相反拥有唯一的极小值点。。。。。。

1.若f(lmid)<f(rmid),分析可知，可能两点在极大值左边/两点在极大值左右，XXX一定

（书上似乎有错误，理解不能，先略过）

 

 

 

 

#include<bits/stdc++.h>
using namespace std;
int a[50001];
int l,n,m,mid,ans;
int half(int x)
{
    int s=0,num=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]-s<x)
        {
            num++;
        }
        else
        {
            s=a[i];
        }
    }
    if(num>m)
    {
        return 0;
    }
    return 1;
}
int main()
{
    /*while(l+1e-5<r)
    {
        double mid=(l+r)/2;
        if(calc(mid))
        {
            r=mid;
        }
        else
        {
            l=mid;
        }
    }*/
    /*for(int i=0;i<100;i++)
    {
        double mid=(l+r)/2;
        if(calc(mid))
        {
            r=mid;
        }
        else
        {
            l=mid;
        }
    }*/
    //int l,n,m;
    cin>>l>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    int ll=0,rr=l;
    a[n+1]=l;
    while(ll<rr)
    {
        mid=(ll+rr+1)/2;
        if(half(mid))
        {
            ll=mid;
            ans=mid;
        }
        else
        {
            rr=mid-1;
        }
    }
    cout<<ans;
    return 0;
}