[C++知识库]二分 模板

对于答案是整数的二分，经常要求解最大合法解或者最小合法解。这样就有边界处理的情况。这里写了一个模板：

以下是求解x^2<=y的最大x的程序。

correlation表示相关性，correlation为-1表示越小越合理，correlation为1表示越大越合理。

judge函数返回三种指，-1：非法；0：刚好为解；1：合法解；

legal_L 需要设置成最小界，legal_R为最大界。而且必须满足至少覆盖合法解和非法解各一个。

EF将会返回judge最接近0的解（刚好为解，或者为合法解）。

#include<bits/stdc++.h>
using namespace std;
const int max_n=1e4+10;

const int legal_L = 0;
const int legal_R = 10001;
int judge(int mid, int query)
{
    if(mid == legal_L) return 1;
    else if(mid == legal_R) return -1;

    //add your judge
    if(mid * mid == query) return 0;
    else if(mid * mid < query) return 1;
    else return -1;
}

// correlation = -1: less is legal
// correlation = 1: large is legal
int EF(int query, int correlation)
{
    int l = legal_L;
    int r = legal_R;
    int mid;
    while(l<=r)
    {
        mid = (l + r ) / 2;
        int jdg = judge(mid, query);
        if(jdg * correlation == 0) return mid;
        else if(jdg * correlation > 0) r = mid - 1;
        else l = mid + 1;
    }
    // l>r 且 judge(l) *judge(r) = -1
    if(correlation > 0) return l;
    else return r;
}

int main()
{
    printf("%d\n",EF(101, -1));
}

对于浮点情况就比较好处理了，一般在l，r中间加一个精度判断就行了：

double EF(int query, int correlation)
{
    double l = legal_L;
    double r = legal_R;
    double mid;
    while(l+0.000001<r)
    {
        mid = (l + r ) / 2;
        int jdg = judge(mid, query);
        if(jdg * correlation == 0) return mid;
        else if(jdg * correlation > 0) r = mid;
        else l = mid;
    }
    return mid;
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖