总阅读量次

　　关于二分算法想必大家也是耳熟能详,但是在实施算法时，往往在细节方面由于没有考虑周全而抓耳挠腮，百思不得其解。这很正常。因为当年在学术界，第一个正确的二分算法写出来就花了20年；又不正常。现在，对于二分算法无论是理论研究还是实际运用都已经很纯熟了，我们既然可以站在巨人的肩膀上，那又何乐而不为呢？

　　这里总结一下一些常用的二分算法的写法。

一、二分查找

　　查找序列为严格递增序列，元素所在区间为[0,n-1]。当元素存在重复时，它不保证返回序列中第一个该元素的索引，故待查找序列不应存在重复元素。

int binarySearch(int l, int r, int x)
{
    int mid;
    while(l <= r)            /* 若此时l==r，还要进行一次查找*/
    {                        /* 当l>r时，查找失败，退出循环*/
        mid = (l + r) / 2;    /* 备注1 */
        if(s[mid] == x)        /* 返回元素所在序列的索引*/
            return mid;
        if(s[mid] > x)
            r = mid - 1;    /* 此时目标元素x存在区间为[l,mid - 1]*/
        else
            l = mid + 1;    /* 此时目标元素x存在区间为[mid + 1,r]*/
    }
    return -1;                /* 没有找到，返回-1*/
}

备注1：此处可能存在 l + r 溢出int范围，所以可以用 l + (r-l)/2避免溢出

二、解析STL中lower_bound和upper_bound

lower_bound(求序列中第一个大于等于目标元素x的索引)

　　查找序列为非递减序列，初始区间为[1,n]——(因为x可能大于序列中所有的元素，此时满足条件的元素就是其本身，此时返回值为n)，

int lower_bound(int l, int r, int x)
{
    int mid;
    while(l < r)            /* 当l==r时，该位置唯一，循环结束*/
    {
        mid = l + (r - l) / 2;
        if(s[mid] >= x)        /* 第一个大于等于x的索引在[l, mid]里 */
            r = mid;
        else
            l = mid + 1;    /* 第一个大于等于x的索引在[mid+1, r]里 */
    }
    return l;
}

upper_bound(求序列中第一个大于目标元素x的索引)

　　查找序列为非递减序列，代码与与上面类似。

int lower_bound(int l, int r, int x)
{
    int mid;
    while(l < r)            /* 当l==r时，该位置唯一，即是目标位置，循环结束*/
    {
        mid = l + (r - l) / 2;
        if(s[mid] > x)        /* 第一个大于x的索引在[l, mid]里 */
            r = mid;
        else
            l = mid + 1;    /* 第一个大于x的索引在[mid+1, r]里 */
    }
    return l;
}

三、二分思想运用

看一道经典题:

给出N个线段长度，试将它们头尾相接组合成一个凸多边形，使凸多边形的外接圆（多边形每个顶点都在圆上）的半径最大，求该最大半径。其中N<=10^5，线段长度均不超过100，要求算法中不涉及坐标的计算。

分析:

思路1

首先，因为圆心不确定，想涉及坐标计算也无能为力啊😂。
其次，考验数学时候来啦。我们可以确定当圆是凸多边形外接圆时，该多边形内角和为$π*(n-2)$，对于每一条弦（题中线段），与两条半径组成等腰三角形，解该等腰三角形其底角为

$$α_{i}=arccos(\frac{s_{i}/2}{r})$$

则凸多边形内角和为$\sum{i=0}^{n-1}α{i}$。此时则可以二分$r$，当内角和小于误差限时，即得到最大半径。

思路2

换一个角度，一条线段(弦)对应的圆心角为

$$α_{i}=arcsin(\frac{s_{i}/2}{r})$$

而当r确定，所有的弦对应的圆心角和$\sum{i=0}^{n-1}α{i}=2π$，此时可以二分$r$，当内角和小于误差限时，即得到最大半径。
思路1和2，C++代码链接：二分思想题解