算法基础 - 二分

bool check(int x) {  } // 检查 x 是否满足二分性质

// 右侧符合答案
int bsearchR(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check()) r = mid;
        // 注意：当 check() 成功后，变换规则： r = mid 时，mid = l + r + 1 >> 1
        else l = mid + 1;
    }

    return l;
}

例
给定一个升序数组如：[1, 3, 5, 5, 7, 9]
需要找到符合大于等于 5 的下标
那么使用该模板，找到的下标为 2

bool check(int x) {  } // 检查 x 是否满足二分性质

// 左侧符合答案
int bsearchL(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check()) l = mid;
        // 注意：当 check() 成功后，变换规则： l = mid 时，mid = l + r + 1 >> 1
        else r = mid - 1;
    }
    
    return l;
}

例
给定一个升序数组如：[1, 3, 5, 5, 7, 9]
需要找到符合小于等于 5 的下标
那么使用该模板，找到的下标为 3

bool check(double x) { ... } // 检查 x 是否满足二分性质

double bsearch(double l, double r)
{
    while (r - l >= 1e-6)  // 当 r - l 小于某一个很小的值后，认为 r/l 相等。
    {
        double mid = (l + r) / 2;
        if (check()) r = mid;
        else l = mid;
    }
    return l;
}