二分アルゴリズム(詳細分類版)

にぶんアルゴリズム
二分検索(整数二分)
1.質問1
厳密な単調シーケンスAにおいて、与えられた数xをどのように見つけるか.
コード#コード#

//          [left, right],       [0, n- 1]
int binarySearch(int A[], int left, int right, int x)
{
    int mid;
    while (left <= right)
    {
        mid = left + right >> 1;
        //mid = left + (right - left) / 2;
        if (A[mid] == x) return mid;
        else if (A[mid] > x)
            right = mid - 1;
        else 
            left = mid + 1;    
    }
    return -1;
}

2.質問2
シーケンス中の最初のx以上の要素の位置Lと、最初のx以上の要素の位置Rを求め、このように要素xがシーケンス中に存在する区間が左閉右開区間[L,R]である.
コード#コード#
(1)シーケンスの最初のx以上の要素の位置を求める.

//          [left, right],  [0, n]
int lower_bound(int A[], int left, int right, int x) 
{
    int mid;
    while (left < right)
    {
        mid = left + right >> 1;
        if (A[mid] >= x)
            right = mid;
        else 
            left = mid + 1;
    }
    return left;       //        
}

注意1.各ループの探索空間は[left,right]左閉右閉、[left,right)左閉右開でもよい.3.left==rightのときwhileループが中止され、このとき探索空間は[left,left]が空であり、leftまたはrightを返してもよい.要素が存在する場合は、条件を満たす位置を返し、逆にその位置を返します.4.2分の初期区間は、戻る可能性のあるすべての結果をカバーすることができるべきである.二分下界は明らかに0であるが、二分上界がnであるかn−1でないかは、クエリの要素がシーケンス内のすべての要素よりも大きい場合にnを返す(すなわち、存在すると仮定し、その位置にあるべきである).従って、二分初期区間[left,right]=[0,n]である.しかし、二分時のnでの値は実際の意味がない.

(2)シーケンス中の最初のxより大きい要素の位置を求める.

//          [left, right],  [0, n]
int upper_bound(int A[], int left, int right, int x)
{
    int mid;
    while (left < right)
    {
        mid = left + right >> 1;
        if (A[mid] > x)
            right = mid;
        else
            left = mid + 1;
    }
    
    return left;
}

3.テンプレートのまとめ
ある条件Cを満たす最初の要素の位置を探す
「条件C」を満たす最後の要素の位置を探すと、まず最初の条件を満たすことができます.
条件!C”
の各見出しページがあります.

//          [left, right]，               
int solve(int left, int right) 
{
    int mid;
    while(left < right)
    {
        mid = left + right / 2;
        if (    )        //    ，              <=mid 
        {
            right = mid;    
        }
        else    //     ，           >mid 
        {
            left = mid + 1; 
        }
    }
    return left; 
}

4.テンプレート拡張(区間左開き右閉)

//          (left, right]，               
int solve(int left, int right) 
{
    int mid;
    while(left + 1 < right)
    {
        mid = left + right / 2;
        if (    )        //    ，              <=mid 
        {
            right = mid;    
        }
        else    //     ，           >mid 
        {
            left = mid; 
        }
    }
    return left; 
}

浮動小数点2分
1.精度ビットでのサイクル終了条件

while(r-l

2.例題
1.$sqrt{2}$の近似値を計算します.

const double eps = 1e-5;
double f(double x)
{
    return x * x - 2;
}

double calSqrt()
{
    double left = 1, right = 2;
    double mid;
    while (right - left > eps)
    {
        mid = (right + left) / 2;
        if (f(mid) > 0)
            right = mid;
        else
            left = mid;
    }
    return mid;    
}

上記の問題は実際にこの問題の特例である:[L,R]に定義された単調関数f(x)を与え,方程式f(x)=0のルートを求める.

const double eps = 1e-5;
double f(double x)
{
    return ....;
}

double solve(double L, double R)
{
    double left = L, right = R;
    double mid;
    while (right - left > eps)
    {
        mid = (right + left) / 2;
        if (f(mid) > 0)
            right = mid;
        else
            left = mid;
    }
    return mid;    
}

2.
木の棒の切断問題:N本の木の棒を与えて、長さは知っていて、今これらの木の棒を切断して少なくともK本の長さの等しい木の棒を得て、長さの等しい木の棒の最長がどれだけ長いかを求めます.

#include 
#include 

using namespace std;

const int N = 110;
int a[N];
int n, k;

int check(int l)
{
    int sum = 0;
    for (int i = 0; i < n;i ++)
        sum += a[i] / l;
    return sum;
}

int solve(int left, int right)
{
    int mid;
    while (left < right)    
    {
        mid = left + right >> 1;
        if (check(mid) < k)
            right = mid;
        else
            left = mid + 1 ;
    }
    
    return left - 1;
}

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i ++)
        scanf("%d", &a[i]);
        
    sort(a, a + n);
    
    int ans = solve(0, a[n-1] + 1);
    
    printf("%d
", ans);
    
    return 0;
}

参考資料『アルゴリズムノート』