ACwing算法基础课听课笔记（第一章，基础算法一）(二分)

　　二分法：

　　　　在看这个视频前，我对于二分法是一头雾水的，又加上这个算法我个人很容易写错emm...。视频提到ACwing上的一道题，我用自以为聪明的方法去做，结果TLE了，实在丢人，不说了，开整！

　　　　对于例题 789：数的范围，寻找一个数前后第一次与最后一次出现的坐标。我们需要这个模板：

　　　　数组定为number[];

　　　　（1）来看第一种情况：如图，假设两个点分别是最先与最后出现的位置。求第一次x出现的位置实际上就是（1）这种情况。那么我们定一个条件

　　　　mid=(l+r)>>1　　if(number[mid]在a中)　　

　　　　　　　　　　　　　　r=mid;　　区间变为[L,mid],　因为mid处可能是答案，所以mid不要加一也不要减一。

　　　　　　　　　　　　 else(落在b中)　　

　　　　　　　　　　　　　　　　　　l=mid+1; 区间变为[mid+1,R]　　

　　　　（2）来看第二种情况：如图，就是求x最后一次出现的位置了。依然是

　　　int mid=(l+r+1)>>1; if(number[mid]在b中)　　

　　　　　　　　　　　　　　　　l=mid 区间变为[mid,R]，mid不要动因为mid处可能是答案

　　　　　　　　　　　　　else　　　　

　　　　　　　　　　　　　　　　r=mid-1　　因为mid处肯定不是答案，所以要减一，区间变为[L,mid-1]；

　　　　但是注意要注意（2）中的(L+r+1)>>1,因为如果 l=r-1时，式子不加一会出现mid=L+1/2,因为向下取整，所以mid=L,进入if后会一直求出区间[L,R]造成死循环，而(1)就不会出现。

　　　　综上，有以下两个模板，分别对应不同的情况

//区间[L,R]被分成[L,mid]和[mid+1,R]时
int bsearch_1(int l,int r)

{

    while(l<r)

    {

        int mid=l+r >>;

        if(check(mid))

            r=mid;

        else

            l=mid+;

    }

}

//区间[L,R]被分成[L,mid-1]和[mid,R]时

int bsearch_2(int l,int r) 
{
　　while(l<r) 
　　{ 
　　　　int mid=l+r+ >>;
　　　　if(check(mid)) 
　　　　　　l=mid;
 　　　else 
　　　　　　r=mid-; }
 　}

　　　然后上789代码　　：　　

#include<iostream>

const int maxn=1e5+;

using namespace std;

int a[maxn];

int n,k;

int main()

{

    cin>>n>>k;

    for(int i=;i<n;i++)

        cin>>a[i];

    while(k--)

    {

        int x;

        cin>>x;

        int l=,r=n-;

        while(l<r)

        {

            int mid=(l+r)>>;

            if(a[mid]>=x)

            {

                r=mid;

            }

            else

            {

                l=mid+;

            }

        }

        if(a[l]!=x)

            cout<<"-1 -1"<<endl;

        else

        {

            cout<<l<<' ';

            int l=,r=n-;

            while(l<r)

            {

                int mid=(l+r+)>>;

                if(a[mid]<=x)

                {

                    l=mid;

                }

                else

                    r=mid-;

            }

            cout<<r<<endl;

        }

    }

}

　　　　再来个手动开方嘿嘿，二分法：

#include<iostream>

using namespace std;

#include<cstdio>

int main()

{

    double x;

    while(cin>>x)

    {

        double l=,r=x;

        while((r-l)>1e-)//精度不够再加，可以时1e-8

        {

            double mid=(l+r)/;

            if(mid*mid>x)

                r=mid;

            else

                l=mid;

        }

        printf("%lf\n",l);

    }

}

　开三次方：ACWING 790

#include<iostream>

#include<cmath>

#include<cstdio>

using namespace std;

int main()

{

    double x;

    while(cin>>x)

    {

        double l,r;

        if(x>=)

            l=,r=x;

        else

            l=x,r=;

        while(fabs(r-l)>1e-)

        {

            double mid = (l+r)/;

            if(mid*mid*mid>x)

                r=mid;

            else

                l=mid;

        }

        printf("%lf\n",l);

    }

}

巴特西

ACwing算法基础课听课笔记（第一章，基础算法一）(二分)

最新文章

热门文章