二分
本页面将简要介绍二分查找,由二分法衍生的三分法以及二分答案。
二分法¶
简介¶
二分查找(英语:binary search),也称折半搜索(英语:half-interval search)、对数搜索(英语:logarithmic search),是用来在一个有序数组中查找某一元素的算法。
工作原理¶
以在一个升序数组中查找一个数为例。
它每次考察数组当前部分的中间元素,如果中间元素刚好是要找的,就结束搜索过程;如果中间元素小于所查找的值,那么左侧的只会更小,不会有所查找的元素,只需到右侧查找;如果中间元素大于所查找的值同理,只需到左侧查找。
性质¶
时间复杂度¶
二分查找的最优时间复杂度为
二分查找的平均时间复杂度和最坏时间复杂度均为
空间复杂度¶
迭代版本的二分查找的空间复杂度为
递归(无尾调用消除)版本的二分查找的空间复杂度为
代码实现¶
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | int binary_search(int start, int end, int key) {
int ret = -1; // 未搜索到数据返回-1下标
int mid;
while (start <= end) {
mid = start + ((end - start) >> 1); // 直接平均可能会溢出,所以用这个算法
if (arr[mid] < key)
start = mid + 1;
else if (arr[mid] > key)
end = mid - 1;
else { // 最后检测相等是因为多数搜索情况不是大于就是小于
ret = mid;
break;
}
}
return ret; // 单一出口
}
|
Note
对于 n >> 1
比 n / 2
指令数更少。
最大值最小化¶
注意,这里的有序是广义的有序,如果一个数组中的左侧或者右侧都满足某一种条件,而另一侧都不满足这种条件,也可以看作是一种有序(如果把满足条件看做
要求满足某种条件的最大值的最小可能情况(最大值最小化),首先的想法是从小到大枚举这个作为答案的「最大值」,然后去判断是否合法。若答案单调,就可以使用二分搜索法来更快地找到答案。因此,要想使用二分搜索法来解这种「最大值最小化」的题目,需要满足以下三个条件:
- 答案在一个固定区间内;
- 可能查找一个符合条件的值不是很容易,但是要求能比较容易地判断某个值是否是符合条件的;
- 可行解对于区间满足一定的单调性。换言之,如果
x x + 1 x - 1
当然,最小值最大化是同理的。
STL 的二分查找¶
C++ 标准库中实现了查找首个不小于给定值的元素的函数 std::lower_bound
和查找首个大于给定值的元素的函数 std::upper_bound
,二者均定义于头文件 <algorithm>
中。
二者均采用二分实现,所以调用前必须保证元素有序。
二分答案¶
解题的时候往往会考虑枚举答案然后检验枚举的值是否正确。若满足单调性,则满足使用二分法的条件。把这里的枚举换成二分,就变成了“二分答案”。
Luogu P1873 砍树
伐木工人米尔科需要砍倒 M 米长的木材。这是一个对米尔科来说很容易的工作,因为他有一个漂亮的新伐木机,可以像野火一样砍倒森林。不过,米尔科只被允许砍倒单行树木。
米尔科的伐木机工作过程如下:米尔科设置一个高度参数 H(米),伐木机升起一个巨大的锯片到高度 H,并锯掉所有的树比 H 高的部分(当然,树木不高于 H 米的部分保持不变)。米尔科就行到树木被锯下的部分。
例如,如果一行树的高度分别为 20,15,10 和 17,米尔科把锯片升到 15 米的高度,切割后树木剩下的高度将是 15,15,10 和 15,而米尔科将从第 1 棵树得到 5 米,从第 4 棵树得到 2 米,共得到 7 米木材。
米尔科非常关注生态保护,所以他不会砍掉过多的木材。这正是他为什么尽可能高地设定伐木机锯片的原因。帮助米尔科找到伐木机锯片的最大的整数高度 H,使得他能得到木材至少为 M 米。换句话说,如果再升高 1 米,则他将得不到 M 米木材。
解题思路
我们可以在 1 到 1,000,000,000(10 亿)中枚举答案,但是这种朴素写法肯定拿不到满分,因为从 1 跑到 10 亿太耗时间。我们可以对答案进行 1 到 10 亿的二分,然后,每次都对其进行检查可行性(一般都是使用贪心法)。 这就是二分答案。
参考代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | int a[1000005];
int n, m;
bool check(int k) { // 检查可行性,k为锯片高度
long long sum = 0;
for (int i = 1; i <= n; i++) // 检查每一棵树
if (a[i] > k) // 如果树高于锯片高度
sum += (long long)(a[i] - k); // 累加树木长度
return sum >= m; // 如果满足最少长度代表可行
}
int find() {
int l = 1, r = 1000000001; // 因为是左闭右开的,所以10亿要加1
while (l + 1 < r) { // 如果两点不相邻
int mid = (l + r) / 2; // 取中间值
if (check(mid)) // 如果可行
l = mid; // 升高锯片高度
else
r = mid; // 否则降低锯片高度
}
return l; // 返回左边值
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
cout << find();
return 0;
}
|
看完了上面的代码,你肯定会有两个疑问:
-
为何搜索区间是左闭右开的?
因为搜到最后,会这样(以合法的最大值为例):
然后会
合法的最小值恰恰相反。
-
为何返回左边值?
同上。
三分法¶
简介¶
三分法可以用来查找凸函数的最大(小)值。
画一下图好理解一些(图待补)
- 如果
lmid
和rmid
在最大(小)值的同一侧:由于单调性,一定是二者中较大(小)的那个离最值近一些,较远的那个点对应的区间不可能包含最值,所以可以舍弃。 - 如果在两侧:由于最值在二者中间,我们舍弃两侧的一个区间后,也不会影响最值,所以可以舍弃。
代码实现¶
1 2 3 4 5 6 | lmid = left + (right - left >> 1);
rmid = lmid + (right - lmid >> 1); // 对右侧区间取半
if (cal(lmid) > cal(rmid))
right = rmid;
else
left = lmid;
|
分数规划¶
参见: 分数规划
分数规划通常描述为下列问题:每个物品有两个属性
经典的例子有最优比率环、最优比率生成树等等。
分数规划可以用二分法来解决。
build本页面最近更新:,更新历史
edit发现错误?想一起完善? 在 GitHub 上编辑此页!
people本页面贡献者:OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用