分治算法

二分算法属于分治算法，有三个步骤

整数二分算法

右分界点

此模板适用于寻找右边部分的分界点，即右分界点

举例来说，对于排好序数组 {1 2 3 4 5 6}

对于二分的性质 ">=3"，数组分成 {1 2} 和 {3 4 5 6} 两部分

左边部分不满足性质 ">=3"，右边部分满足性质 ">=3"

算法寻找的点就是数组元素 3 的下标，即所谓的右分界点

如果寻找左分界点(例:对于性质"<3",左分界点就是数组元素2的下标)，该算法就要做相应的修改

模板

int bsearch_1(int l, int r)
{
    //第二步：递归处理子问题，用while循环来实现
    while (l < r)
    {
        //第一步：分解成子问题,这是二分的核心--范围减半
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    //向左边找 //if判断mid是否满足性质，注意该性质会划分数组的右边部分
        else l = mid + 1;           //向右边找
    }
    //第三步：合并子问题.对二分算法来说，不需要这一步
    return l;   //l就是寻找的右分界点,如果数组中没有要找的点，l的值就是r,但这是一个错误答案
}

待证问题：循环结束后的l就是要找的点(默认包含答案)

证明

循环不变式：[l..r]中包含答案点res

1. 初始

   显然[l..r]包含答案点res

2. 保持

   假设某轮循环开始之前,[l..r]包含答案点res

   执行循环体

   int mid = l + r >> 1 mid是向下取整得到的

   if语句分支1：

   如果mid满足性质，那么说明res在[l..mid]间(包括mid本身),令 r = mid

   if语句分支2：

   如果 mid 不满足性质，说明mid在左边部分，res在[mid+1..r]间,令l = mid + 1

   ∴ l和r更新之后，下一轮循环开始之前，循环不变式依然成立

3. 终止

   循环终止时， l >= r

   易知 l不可能比 r 大 , 故 l = r

   ∴ 根据循环不变式，l 就是答案点 res

边界分析

问题：为什么 mid 是向下取整得到的，即 mid = l + r >> 1. 而不是向上取整,即 mid = l + r + 1 >> 1

答：mid向下取整是为了缩小范围，避免造成无限划分

证明：

if语句分支1： r = mid = l + r >> 1 (向下取整) 一定小于原来的 r

if语句分支2： l = mid + 1 一定大于原来的 l

所以，mid向下取整的话，就不会造成无限划分

注：对于二分的另一种情况，即寻找左分界点, mid就需要向上取整了

寻找左分界点

int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;   // mid 向上取整
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

浮点数二分

浮点数二分算法和整数的两种算法一摸一样，只不过不需要考虑向上取整还是向下取整，以及边界处理

浮点数寻找右分界点

double bsearch_3(double l, double r)
{
    while (r - l > 精度)
    {
        double mid = (l + r) / 2;   //这里不需要考虑取整，因为是浮点数
        if (check(mid)) r = mid;    //这里需不需要考虑 +1 -1 之类的，因为是浮点数
        else l = mid;
    }
    return l;
}

浮点数寻找左分界点

double bsearch_4(double l, double r)
{
    while (r - l > 精度)
    {
        double mid = (l + r) / 2;
        if (check(mid)) l = mid;    //只有这两个地方与上面的模板相反，其余都一样
        else r = mid;
    }
    return l;
}

二分算法的证明和边界分析