二分

                     

贡献者： 有机物

　　 二分（查找）是个很强的算法，二分也是个很麻烦的算法，因为有很多边界问题。

　　 据说，只有 $10 \%$ 的程序员能写对二分。二分的写法有很多，选一种自己习惯的写法就行。Um_Nik 的名言：“停止学习无用算法，二分查找解决问题！”

　　 二分的本质不是单调性，有单调性的问题一定能二分，但能二分的问题可以不具有单调性。因此二分的本质是二段性。具体来讲，一段区间，使得左半边满足一个性质，右半边不满足、左半边不满足一个性质，而右半边满足。所以可以通过二分查找来找到这个分界点。

　　 二分查找算法每次把区间一分为二使搜索范围缩小一半，所以二分的时间复杂度为 $\mathcal{O}(\log_2 n)$。

　　 以一个具体的例子看二分：

　　 给定一个按照升序排列的长度为 $n$ 的整数数组 $a$，以及 $q$ 个查询。 对于每个查询，返回一个元素 $x$ 的起始位置和终止位置（位置从 $0$ 开始计数）。如果数组中不存在该元素，则返回 -1 -1。

　　 样例：

左半边输入，右半边输出
6 3
1 2 2 3 3 4
3             3 4
4             5 5
5            -1 -1

　　 假设要二分一下 $3$ 的起始位置，设置二分分界点为 $\dfrac{l+r}{2}$，每次判断一下二分条件，再划分边界。

　　 这里的二分条件有两种情况。

1. 判断一下分界点是不是不小于 $3$，如果判断条件成立，则说明答案在左半边区间，则应该把右半边区间缩小。相反（分界点小于 $3$），则说明答案在右半边区间，则应该把左半边区间缩小。
2. 判断一下分界点是不是小于 $3$，如果判断条件成立，则说明答案在右半边区间，则应该把左半边区间缩小。相反（分界点不小于 $3$），则说明答案在左半边区间，则应该把右半边区间缩小。

　　 可见这两种情况是相对应的，可以根据自身习惯选择其中一种写法。

// 二分查找 x 的起始位置

int l = 0, r = n - 1;

// 写法一
while (l < r)
{
	int mid = l + r >> 1;  // (l + r) / 2
    if (a[mid] >= x) r = mid;
    else l = mid + 1;
}

// 写法二
while (l < r)
{
    int mid = l + r >> 1;
    if (q[mid] < x) l = mid + 1;
    else r = mid;
}

　　 二分查找 $x$ 的终止位置也与查找起始位置类似。

　　 这里的二分条件同样也有两种情况。

1. 判断一下分界点是不是不大于 $3$，如果判断条件成立，则说明答案在右半边区间，应该把左半边区间缩小。相反缩小右半边区间。
2. 判断一下分界点是不是大于 $3$，如果判断条件成立，则说明答案在左半边区间，应该把右半边区间缩小。相反缩小左半边区间。

// 二分查找 x 的终止位置

int l = 0, r = n - 1;

// 写法一
while (l < r)
{
	int mid = l + r + 1 >> 1;  // (l + r + 1) / 2
    if (a[mid] <= x) l = mid;
    else r = mid - 1;
}

// 写法二
while (l < r)
{
    int mid = l + r + 1 >> 1;
    if (q[mid] > x) r = mid - 1;
    else l = mid;
}

　　 还有一点边界情况需要注意，当二分查找 $x$ 的终止位置时，分界点要多加 $1$。

　　 简单的证明一下：

　　 因为当有 $l, r$ 两个位置只差一的时候，有 $l = r - 1, r = l + 1$，当不补上加一的时候，计算分界点时 $\frac{r - 1 + l + 1}{2} = \frac{l+r}{2}=l$（C++ 除法是下取整），当判断条件分界点不大于 $x$ 成立时，执行 l = mid 之后 l = mid = l，所以就会陷入死循环中。所以需要补上加一。