目錄

??前言：

?? 二分的概念

?? 整數(shù)二分

?? 二分的模板

?? 習題

?? 總結

??前言：

????????這篇文章主要是準備藍橋杯競賽同學所寫，為你更好準備藍橋杯比賽涉及的算法知識點。不知道你是否苦惱于不知算法從何學起，苦惱于網(wǎng)上資料稀少，或者復雜難懂，這篇文章就是幫助這部分同學的。

? ? ? ? 下面整理了藍橋杯考點大綱：

???????????????藍橋杯考點大綱

??

? ? ? ? 通過上圖，我們知道二分在藍橋杯比賽中也是比較重要的，所以我們這里就單獨寫了一篇文章介紹，不僅是因為比較重要，而且二分算法對于剛接觸算法的人來說比較復雜，易錯點較多，需要不斷調試。

?? 二分的概念

? ? ? ? 二分，字面意思就是通過判斷是否滿足條件將區(qū)間分成兩份。通常的比如大于等于 或者? 小于等于.......

?? 整數(shù)二分

? ? ? ? 對于整數(shù)二分，我們可以分成兩中類型 ：

? ? ? ? 1. [L ，Mid - 1] 和 [Mid , R] ：所求答案在Mid 右邊

? ? ? ? 2. [L , Mid ] 和 [Mid + 1 , R] ：所求答案在Midz左邊

? ? ? ? 這兩種不同類型的區(qū)間，是由于判斷條件不同形成的。

?? 二分的模板

? ? ? ? 為了大家更好的做題，已經(jīng)比賽中更好的利用時間，這里提供了整數(shù)二分的模板，以及浮點數(shù)二分的模板。

1) 區(qū)間[L , R] 劃分成[L,Mid] 和 [Mid+1 , R]
bool check(int x)
{
    ...    //檢查x是否滿足某種條件
}
int bearch_1(int l,int r)
{
    while(l < r)
    {
        int mid = (l + r ) / 2;
        if(check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    return 1;
}

2) 區(qū)間[L , R] 劃分成[L,Mid-1] 和 [Mid , R]
bool check(int x)
{
    ...    //檢查x是否滿足某種條件
}
int bearch_2(int l,int r)
{
    while(l < r)
    {
        int mid = (l + r + 1 ) / 2;
        if(check(mid))
            l = mid;
        else
            r = mid - 1;
    }
    return 1;
}

? ? ? ? 對于浮點數(shù)二分，并不需要關注+-1的問題，所以相對于整數(shù)二分來說，簡單一些。當然一般來說，對于浮點數(shù)二分，我們需要保證精確度在1e-6（1的-6次方）。

bool check((int x)
{
    ...    //檢查x是否滿足條件
}

int bearch_1(int l,int r)
{
    while(r - l > 1e-6 )
    {
        int mid = (l + r ) / 2;
        if(check(mid))
            r = mid;
        else
            l = mid ;
    }
    return 1;
}

?? 習題

1. 數(shù)的范圍?789. 數(shù)的范圍 - AcWing題庫

? ? ? ? 這道題其實就是一道非常經(jīng)典的二分題目，首先我們找出左邊第一次出現(xiàn)的x,再找出右邊第一次出現(xiàn)的x，如果沒有找到，則輸出-1 -1。

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 100010;

int q[N];
int n,m;


int main()
{
    
    cin >> n>>m;
    for(int i=0;i<n;i++)
        cin>>q[i];
    
    while(m--)
    {
        int x;
        cin>>x;
        int l = 0;
        int r = n-1;
        while(l < r)
        {
            int mid = (l + r) >> 1;
            if(q[mid] >= x)
                r = mid;
            else
                l = mid + 1;
        }
        if(q[l] != x)
            printf("-1 -1\n");
        else
        {
            printf("%d ",l);
            r = n-1;
            while(l < r)
            {
                int mid = (l + r + 1) >> 1;
                if(q[mid] <= x)
                    l = mid;
                else
                    r = mid -1;
            }
            printf("%d\n",l);
        }
    }
    return 0;
}

2.數(shù)的三次方根?790. 數(shù)的三次方根 - AcWing題庫

? ? ? ? 我們從數(shù)據(jù)范圍當做區(qū)間，通過二分找出浮點數(shù)n的三次方根。

#include <iostream>
#include <cstdio>

using namespace std;

int main()
{
    double x ;
    cin >> x;
    double l = -10000,r =10000;
    while(r -l > 1e-8)
    {
        double m = (r + l) /2;
        if(m * m * m >= x)
            r = m;
        else
            l = m;
    }
    printf("%lf",l);
    return 0;
}

?? 總結

? ? 以上，我們就對二分在藍橋杯中的知識點進行了講解，并針對性的講解了例題，當然這也只是幫你更好的理解這些算法知識，想要學好算法，還需要不斷地刷題練習，這里推薦到洛谷，acwing等網(wǎng)站進行練習，比如你看完了這篇文章，做回了例題習題，就可以上這些網(wǎng)站進行想應的練習。

文章來源地址http://www.zghlxwxcb.cn/news/detail-799784.html

到了這里，關于藍橋杯備賽 day 2 —— 二分算法（C/C++，零基礎，配圖）的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！