＜算法基础＞二分查找

        相较于网络上其他两种二分模板，更优雅的二分模板是左开右开区间模板

• l + 1 = r时结束
• 可行区的指针最后一定指向答案
• 开区间可以正确处理边界

一、整数二分查找

1. 最大化查找：

最大化查找：查找最后一个<=q的下标
int find(int q)
{
    int l = 0, r = n + 1;
    while (l + 1 < r)
    {
        int mid = l + r >> 1;
        if (a[mid] <= q)    l = mid;
        else    r = mid;
    }

    return l;
}

2. 最小化查找：

最小化查找：查找最后一个>=q的下标
int find(int q)
{
    int l = 0, r = n + 1;
    while (l + 1 < r)
    {
        int mid = l + r >> 1;
        if (a[mid] >= q)    r = mid;
        else    l = mid;
    }

    return r;
}

        最终要返回哪一个指针，是要看你要查找的答案被分在了哪半边区域，如果是右边，那么答案就是r，如果是左边，那么答案就是 l

二、浮点数二分查找

1. 最大化查找

例如：求一个浮点数（-10000 <= y <= 10000）的三次方根

double find(double y)
{
    double l = -100, r = 100;
    while (r - l > 1e-5)
    {
        >>右移操作符只适用于整形，浮点型不可以使用，因为存储方式不同
        double mid = (l + r) / 2;
        if (mid * mid *mid <= y)    l = mid
        else    r = mid;
    }
    return l;
}

int main()
{

    double y; sacnf("%lf", &y);
    printf("%.3lf\n", find(y));
    
    return 0;
}