二分——頭疼的邊界

關于acwing

二分

哈羅，大家好，我是cht。

二分的思路

從前有這麼一道題，說：

如何用10個砝碼撐出1-1023的重量？

大家仔細考慮下這題，相信大家都已經有答案了。

1,2,4,8,16,32,64,128,256,512這十個砝碼。

再來一題：

有一棟高樓，怎麼用最少的次數知道它最多在幾層被抛下是不會碎？

答案就是是二分。

好，接下來我們步入正軌，到底什麼是二分？

請看圖：

這就是二分，一次可以排除幾乎一半的答案。

是以我個人覺得二分就是枚舉的一種優化。

先讓大家看看二分有多nb。

假設共有一億種答案，二分算30來此也就夠了！

不信的童鞋們算算1024乘1024乘1024

接下來說說二分的兩種情況

情況1：整數二分

整數二分就是整數情況下的二分，比較難做。

情況2：浮點數二分

浮點情況的二分，幾行搞定！

下面是模闆

1、整數二分模闆1

int l = 0, r = n - 1;
while(/*......*/)//條件，因題而異
{
    int mid = l + r >> 1;
    if(/*......*/) r = mid;//中間為符不符合條件（寫>=）
    else l = mid + 1;
}
cout <</*......*/    << l << /*......*/;
           

2、整數二分模闆2

int l = 0, r = n - 1;
while(/*......*/)//條件，因題而異
{
    int mid = l + r + 1 >> 1;//注意要加1！！！
    if(/*......*/) l = mid;//中間為符不符合條件（寫<=）
    else r = mid - 1;
}
cout <</*......*/    << l << /*......*/;
           

3、浮點數二分模闆（其實和上面一樣）

double l = /*......*/,r = /*......*/;
while(/*......*/)
{
    double mid = (l + r) / 2;
    if(/*......*/) r = mid;
    else l = mid;
}
printf("%.*lf\n", l)//*代表保留幾位小數
           

最後來兩道題（選自算法基礎課）

1、數的範圍

題目描述

給定一個按照升序排列的長度為n的整數數組，以及 q 個查詢。

對于每個查詢，傳回一個元素k的起始位置和終止位置（位置從0開始計數）。

如果數組中不存在該元素，則傳回“-1 -1”。
           

資料範圍

1≤n≤100000
1≤q≤10000
1≤k≤10000
           

樣例

輸入樣例：
6 3
1 2 2 3 3 4
3
4
5
輸出樣例：
3 4
5 5
-1 -1
           

代碼

#include<iostream>

using namespace std;

const int N = 100010;

int n, m;
int q[N];

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i ++) cin >> q[i];
    while(m --)
    {
        int x;
        cin >> x;
        
        int l = 0, 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) cout << "-1 -1" << endl;
        else 
        {
            cout << l << ' ';
            
            int l = 0, r = n - 1;
            while(l < r)
            {
                int mid = l + r + 1 >> 1;
                if(q[mid] <= x) l = mid;
                else r = mid - 1;
            }
            cout << l << endl;
        }
    }
    
    return 0;
}
           

2、數的三次方根

題目描述

給定一個浮點數n，求它的三次方根。
           

資料範圍

−10000≤n≤10000
           

樣例

輸入樣例：
1000.00
輸出樣例：
10.000000
           

代碼

#include<iostream>

using namespace std;

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

好了，今天cht就先跟大家聊到這裡

大家可以看看闫學燦巨佬的課以了解更多有關二分的知識。

有錯誤請多多指正

bye!!!