二分法和三分法是算法竞赛中常见的算法思路,本文介绍了它们的理论背景、模板代码、典型题目。
二分法的理论背景
在《计算方法》教材中,关于非线性方程的求根问题,有一种是二分法。
方程求根是常见的数学问题,满足方程:
f(x) = 0 (1-1)
的数x’称为方程(1-1)的根。
所谓非线性方程,是指f(x)中含有三角函数、指数函数或其他超越函数。这种方程,很难或者无法求得精确解。不过,在实际应用中,只要得到满足一定精度要求的近似解就可以了,此时,需要考虑2个问题:
(1)根的存在性。用这个定理判定:设函数在闭区间[a, b]上连续,且f(a) ∙ f(b) < 0,则f(x) = 0存在根。
(2)求根。一般有两种方法:搜索法、二分法。
搜索法:把区间[a, b]分成n等份,每个子区间长度是∆x,计算点xk = a + k∆x (k=0,1,2,3,4,…,n)的函数值f(xk),若f(xk) = 0,则是一个实根,若相邻两点满足f(xk) ∙ f(xk+1) < 0,则在(xk, xk+1)内至少有一个实根,可以取(xk+ xk+1)/2为近似根。
二分法:如果确定f(x)在区间[a, b]内连续,且f(a) ∙ f(b) < 0,则至少有一个实根。二分法的操作,就是把[a, b]逐次分半,检查每次分半后区间两端点函数值符号的变化,确定有根的区间。
什么情况下用二分?两个条件:上下界[a, b]确定、函数在[a, b]内单调。
图1.1单调函数
复杂度:经过n次二分后,区间会缩小到(b - a)/2n。给定a、b和精度要求ε,可以算出二分次数n,即满足(b - a)/2n <ε。所以,二分法的复杂度是O(logn)的。例如,如果函数在区间[0, 100000]内单调变化,要求根的精度是10-8,那么二分次数是44次。
二分非常高效。所以,如果问题是单调性的,且求解精确解的难度很高,可以考虑用二分法。
在算法竞赛题目中,有两种题型:整数二分、实数二分。整数域上的二分,注意终止边界、左右区间的开闭情况,避免漏掉答案或者死循环。实数域上的二分,需要注意精度问题。
整数二分模板
2.1 基本形式
先看一个简单问题:在有序数列a[]中查找某个数x;如果数列中没有x,找它的后继。通过这个问题,给出二分法的基本代码。
如果有x,找第一个x的位置;如果没有x,找比x大的第一个数的位置。
图2.1 (a)数组中有x(b)数组中没有x
示例:a[] = {-12,-6,-4,3,5,5,8,9},其中有n = 8个数,存储在a[0]~a[7]。
1)查找x = -5,返回位置2,指向a[2] = -4;
2)查找x = 7,返回位置6,指向a[6] = 8;
3)特别地,如果x 大于最大的a[7] = 9,例如x = 12,返回位置8。由于不存在a[8],所以此时是越界的。
下面是模板代码。
查找大于等于 x的最小的一个的位置(x或者x的后继)
int bin_search(int *a, int n, int x){//a[0]~a[n-1]是单调递增的int left = 0, right = n; //注意:不是 n-1while (left < right) {int mid = left + (right-left)/2; //int mid = (left + right) >> 1; if (a[mid] >= x) right = mid;else left = mid + 1;}//终止于left = rightreturn left;//特殊情况:a[n-1] < x时,返回n}
下面对上述代码进行补充说明:
(1)代码执行完毕后,left==right,两者相等,即答案所处的位置。
(2)复杂度:每次把搜索的范围缩小一半,总次数是log(n)。
(3)中间值mid
中间值写成mid = left + (right-left)/2 或者mid = (left + right) >> 1都行 [参考李煜东《算法竞赛进阶指南》26页,有mid = (left + right) >> 1的细节解释]。不过,如果left + right很大,可能溢出,用前一种更好。
不能写成 mid = (left + right)/2; 在有负数的情况下,会出错。
二分法习题
饥饿的奶牛/problem/P1868
寻找段落/problem/P1419
小车问题/problem/P1258
借教室/problem/P1083
跳石头/problem/P2678
聪明的质监员/problem/P1314
分梨子/problem/P1493
第k大http://acm./showproblem.php?pid=6231
如果觉得《最简单易懂二分法详解》对你有帮助,请点赞、收藏,并留下你的观点哦!