二分

                     

贡献者: 有机物

   二分(查找)是个很强的算法,二分也是个很麻烦的算法,因为有很多边界问题.

   据说,只有 $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;
}

图
图 1:查找起始位置

   二分查找 $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,所以就会陷入死循环中.所以需要补上加一.

图
图 2:查找终止位置

致读者: 小时百科一直以来坚持所有内容免费,这导致我们处于严重的亏损状态。 长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。 因此,我们请求广大读者热心打赏 ,使网站得以健康发展。 如果看到这条信息的每位读者能慷慨打赏 10 元,我们一个星期内就能脱离亏损, 并保证在接下来的一整年里向所有读者继续免费提供优质内容。 但遗憾的是只有不到 1% 的读者愿意捐款, 他们的付出帮助了 99% 的读者免费获取知识, 我们在此表示感谢。

                     

友情链接: 超理论坛 | ©小时科技 保留一切权利