学习笔记 - 二分查找与答案（附归并模版、前缀和、差分）

二分算法

二分也就是二分查找，又叫折半查找。这种算法正如其名，每一次都要分一半。
二分算法可以分为二分查找和二分答案。
以在一个升序数组中查找一个数为例，每次考察数组当前部分的中间元素，如果中间元素刚好是要找的，就结束搜索过程；如果中间元素小于所查找的值，那么左侧的只会更小，不会有所查找的元素，只需到右侧查找；如果中间元素大于所查找的值同理，只需到左侧查找。
二分查找和二分答案有什么区别？

二分查找：在一个已知的有序数据集上进行二分地查找
二分答案：答案有一个区间，在这个区间中二分，直到找到最优答案
二分查找侧重于查找一个元素是否存在，而二分答案则侧重于找到答案。

二分查找

当我们要从一个序列中查找一个元素的时候，最快想到的方法就是暴力查找，但这种方法在数据量大时往往会超时，适用于元素较少的时候，一旦元素个数多起来，效率是非常低下，所以在实际中这种查找的方法是很少见的。

假设一个有序数组的长度为 $n$，查找一个数字，且这个数字在数组中，则直接暴力的最坏时间复杂度为 $O(n-1)$（最坏情况是这个数字在最后一个，那么遍历到倒数第二个的时候就已经知道最后一个是要查找的数了），而二分查找的最坏时间复杂度是 $O(log\ n)$，很显然，这种情况下，二分才是最优解。

二分查找法，是简单且效率较高的查找方法，又称折半查找法，但该方法是建立在数组有一定前提下的。

二分查找法的前提条件是：查找的序列必须是有序的（单调性），即该序列中的所有元素都是按照升序或者降序排列好的，如果数组乱序，那么比较后标记左右区间范围就是混乱的，元素与元素只间的差值虽然是随机的，但始终是在递增或递减。

数字炸弹的游戏大家应该都玩过，如果按顺序猜数，效率肯定没有从中间猜那么高，然而，二分查找与数字炸弹的逻辑几乎相同。

二分查找的核心步骤：

① 要有范围和查找值初始状态：数组的首尾各有一个标记，分别记为left和right

接下来就要进行二分，用变量 $mid$ 标记中间值的下标，然后可得变量 $mid$
的计算公式为 $mid=(left+right)\ /\ 2$，而要查找的数组下标的范围是 $[left,\ right]$。
② 此时可以用 $while$ 循环来判断要查找数字的位置，则此时循环的执行条件是 $left<right$，因为 $left$ 和 $right$ 在二分过程中找数字的过程中总是相互靠近，直至指向同一个位置。所以 $left>=right$ 时循环才停止，当 $left==right$ 时，已经查找到了这个数字，此时这个数字的下标是 $left$。当 $left>right$ 且数字未被找到时，说明这个数字不在列表中。
③ 以升序数组的二分查找为例，设这个列表为 $a$，下标范围为 $[left,\ right]$，中间值是 $m$，要查找的数是 $key$。现在要将 $a[m]$ 与要查找的数 $key$ 作比较。
如果 $a[m]$ 小于 $key$，说明 $key$ 在 $a[m]$ 右侧，则将数组从左向右压缩一半，把 $left$ 向右推，推到 $m$ 的右边，相当于把左边的数据都屏蔽了，因为 $key$ 不可能在左半边。
同理，如果 $a[m]$ 大于key，说明 $key$ 在 $a[m]$ 左侧，则将数组从右向左压缩一半，把 $right$ 向左推，推到 $m$ 的左边，$key$ 不可能在右半边。

二分查找板子：

bool binary_search(int x) {
    int l = 1, r = n;
    while (l < r) {
        int mid = l + r >> 1;
        if (a[mid] >= x) r = mid;
        else l = mid + 1;
    }
    if (a[l] == x) return l;
    return 0;
}

二分查找模板相关例题：P2249 查找、P1177 排序、P1226 快速幂（快速幂其实就是一个二分求模的过程，思路：$t^N\ = (t\ \ t)^{N/2}\ \ (N\ %\ 2)$。
二分查找相关题目：https://www.luogu.com.cn/training/459454 $(T1-T5)$

二分答案

解题的时候往往会考虑枚举答案然后检验枚举的值是否正确。若满足单调性，则满足使用二分法的条件，把这里的枚举换成二分，就变成了二分答案。
答案属于一个区间，当这个区间很大时，暴力肯定会超时，重要的是这个区间是对题目中的某个量有单调性的，此时，我们就会二分答案。每一次二分会做一次判断，看是否对应的那个量达到了需要的大小。
如何判断？根据题意写个 $check$ 函数，来检查序列中每一项是否为正确解，如果满足 $check$，就放弃右半区间（或左半区间），如果不满足，就放弃左半区间（或右半区间），一直往复，直至到最终的答案，放弃的区间是根据题意来判断的。
如何判断一个题是不是用二分答案做的呢?
常见描述：求…最大值的最小、求…最小值的最大。
1. 求某序列最大值的最小时，我们二分答案，二分最大值判断条件满足后，尽量让答案往前来，即让 $right=mid-1$。
1. 求某序列最小值的最大时，我们二分答案，二分最小值，判断条件满足后，尽量让答案往后走，即让 $left=mid$。

二分答案的前提：

1.答案在一个区间内；
2.直接正向做不好做，但容易判断一个答案可行不可行；
3.若有多个答案满足题意，则这些答案具有如下特点：若答案 $x$ 满足，则答案范围内小于 $x$ 或大于 $x$ 的答案均满足。

以一次函数 $y=kx+b$ 为例，已知 $y \le c$。要我们在区间 $[m，n]$ 内找到一个数，让其对应的 $y$ 达到要求。

由图可知，$x$ $\in$ $[m,\ a]$ 都是满足的，因此最优解就是 $a$，所以，我们在区间 $[m，n]$ 中采用二分查找的方法，就能找到这个 $a$。

二分答案板子

bool check(int x) {
	int cnt = 0, ans = 0;
	for (int i = 1; i <= n; i++) {
		if (cnt + a[i] <= x) {
			cnt += a[i];
		} else {
			cnt = a[i];
			ans++;
		}
	}
	return ans >= m;
}

while (l <= r) {
	mid = (l + r) / 2;
	if (check(mid)) {
		ans = mid;
		l = mid + 1;
	} else {
		r = mid - 1;
	}
}

T1：P1571 眼红的Medusa

直接打暴力 $20pts$ R145312193
将第二个数组sort排序，用二分依次查找第一个数组中的每一个数字，找到了输出，$100pts$ R145313178

T2：P1182 数列分段 Section II

答案最小可能是数列中的最大值（记为 $l$ )，最大可能是所有数的和（记为 $r$ ）。其次，我们发现，给出一个解，判定这个解是否合法即可，我们可以用枚举答案再判定的方法解决此题。

二分,二分建立在答案的基础上。答案的排布，是有一定规律的，即存在一个分界点 $mid$，使得区间 $[l,mid]$ 中的数都是非法解，$[mid,r]$ 中的数都是可行解。而 $mid$ 为所求的最小解。

$100pts$ R145400899

T3：P2678 跳石头

$20pts$：暴力
$50pts$：考虑 DP，$f[i][j]$ 表示在前 $i$ 块石头移走 $j$ 块石头的最短距离
$60pts$：贪心，每次删除间距最小的，用堆维护
$100pts$：二分答案后贪心，先二分这个距离使其变为判断可行性问题，然后从前往后，一旦这个石头到上一个选的石头的距离小于这个二分的答案就把这块石头移走，最后看移的次数是否与要求的相符合。R145324398

$★$ T4：P1314 聪明的质检员

根据题意，$W$ 越大，矿石选的越少，$W$ 越小，矿石选的越多.所以，随着 $W$ 增大，$Y$ 值减小.所以，二分的判断条件出来了：

当 $y > s$ 时，需要增大 $W$ 来减小 $y$,从而让 $|y-s|$ 变小。
当 $y == s$ 时，$|y-s|==0$。
当 $y < s$ 时，需要增大 $W$ 来减小 $y$,从而让 $|y-s|$ 变大，即可用二分答案完成。
最后再用前缀和套已有的公式计算。
$100pts$：R145428579，友情提示：请注意数据范围和 $maxn$ 和 $minn$ 的初始值。

二分答案相关题目：https://www.luogu.com.cn/training/459454 $(T10-T20)$

附

归并算法模版

void merge(int x[], int l, int mid, int r)
{
	int L[50]{}, R[50]{};
	for (int i = 0; i < mid - l + 1; i++)
	{
		L[i] = x[l + i];
	}
	for (int j = 0; j < r - mid; j++)
	{
		R[j] = x[mid + 1 + j];
	}
	L[mid - l + 1] = INT_MAX;//从小到大排
	R[r - mid] = INT_MAX;
	int i = 0, j = 0;
	for (int k = l; k < r + 1; k++)
	{
		x[k] = L[i] < R[j] ? L[i++] : R[j++];//从小到大排
	}
}
void mergeSort(int x[], int l, int r)
{
	if (l < r)
	{
		int mid = (l + r) / 2;
		mergeSort(x, l, mid);
		mergeSort(x, mid + 1, r);
		merge(x, l, mid, r);
	}
}

最大字段和模版

int maxLR(int x[], int l, int r)
{
	int mid = (l + r) / 2;
	int sumL = 0, sumR = 0, maxL = 0, maxR = 0;
	for (int i = mid; i >= l; i--)
	{
		sumL += x[i];
		maxL = max(sumL, maxL);
	}
	for (int i = mid + 1; i <= r; i++)
	{
		sumR += x[i];
		maxR = max(sumR, maxR);
	}
	return maxL + maxR;
}
int maxSum(int x[], int l, int r)
{
	if (l == r) return x[l] >= 0 ? x[l] : 0;
	int mid = (l + r) / 2;
	int L = maxSum(x, l, mid);
	int R = maxSum(x, mid + 1, r);
	int LR = maxLR(x, l, r);
	int max = L > R ? L : R;
	return max = LR > max ? LR : max;
}

前缀和

前缀和数组的每一项是可以通过原序列以递推的方式推出来的，递推公式就是：$S[i] = S[ i - 1 ] + A[ i ]$。$S[ i - 1 ]$ 表示前 $i - 1$ 个元素的和，在这基础上加上 $A[ i ]$，就得到了前 $i$ 个元素的和 $S [ i ]$。

差分

利用差分可以实现对前缀和数组中的一段区间的元素均加上常数 $C$ 。例如：给定前缀和数组 $S$，$S$ 的差分数组 $A$ ，现在我们要将前缀和数组 $S$ 中 $[ l, r ]$ 区间的所有元素加上常数 $C$，用循环显然需要 $O(N)$ 的时间复杂度。但是如果我们求出来前缀和数组 $S$ 的差分数组 A，那么我们就可以在差分数组中让 $A[ l ] + C$，同时让 $A[ r + 1 ] - C$，此时的差分数组对应的前缀和数组即是目标数组。这样我们就在 $O(1)$ 的时间复杂度里面达到了想要的结果，尽管差分的空间复杂度比遍历要高。

部分参考资料

https://blog.csdn.net/m0_73096566/article/details/129129517
https://blog.csdn.net/m0_73096566/article/details/129135098
https://blog.csdn.net/bubblecheese/article/details/129270040
https://www.cnblogs.com/TFLS-gzr/p/11225057.html
https://img-blog.csdnimg.cn/img_convert/1f6c94195a0d777a08046f97efc444f2.png
https://blog.csdn.net/Colicsin/article/details/125447831
https://www.cnblogs.com/TFLS-gzr/p/11243629.html
https://www.luogu.com.cn/blog/thoq/solution-p1182
https://www.luogu.com.cn/blog/codinging/solution-p1314#
https://www.luogu.com.cn/blog/user31611/solution-p2678

学习笔记

#二分 #算法

学习笔记 - 信息学竞赛中的持久化数据结构与技巧上一篇

游记 - NOIWC 2024 下一篇