二分法和三分法是算法竞赛中常见的算法思路，本文介绍了它们的理论背景、模板代码、典型题目。
二分法的理论背景
在《计算方法》教材中，关于非线性方程的求根问题，有一种是二分法。
方程求根是常见的数学问题，满足方程：
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
如果觉得《最简单易懂二分法详解》对你有帮助，请点赞、收藏，并留下你的观点哦！
