本系列是这本算法教材的扩展：《算法竞赛入门到进阶》(京东 当当) 清华大学出版社 PDF下载地址：https://github.com/luoyongjun999/code 其中的“补充资料” 如有建议，请联系：（1）QQ 群，567554289；（2）作者QQ，15512356

  二分法和三分法是算法竞赛中常见的算法思路，本文介绍了它们的理论背景、模板代码、典型题目。

  在《计算方法》教材中，关于非线性方程的求根问题，有一种是二分法。 　　方程求根是常见的数学问题，满足方程： 　　　　　　　　　 \(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，计算点\(x_k = a + k∆x\), \((k=0,1,2,3,4,...,n)\)的函数值\(f(x_k)\)，若\(f(x_k) = 0\)，则是一个实根，若相邻两点满足\(f(x_k) ∙ f(x_{k+1}) < 0\)，则在\((x_k, x_{k+1})\)内至少有一个实根，可以取(\(x_k+ x_{k+1})/2\)为近似根。 　　二分法：如果确定\(f(x)\)在区间\([a, b]\)内连续，且\(f(a) ∙ f(b) < 0\)，则至少有一个实根。二分法的操作，就是把\([a, b]\)逐次分半，检查每次分半后区间两端点函数值符号的变化，确定有根的区间。 　　什么情况下用二分？两个条件：上下界\([a, b]\)确定、函数在\([a, b]\)内单调。

  复杂度：经过n次二分后，区间会缩小到\((b - a)/2^n\)。给定\(a\)、\(b\)和精度要求\(ε\)，可以算出二分次数\(n\)，即满足\((b - a)/2^n > 1; if (a[mid] >= x) right = mid; else left = mid + 1; } //终止于left = right return 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; 在有负数的情况下，会出错。 　　（4）对比测试 　　bin_search()和STL的lower_bound()的功能是一样的。下面的测试代码，比较了bin_search()和lower_bound()的输出，以此证明bin_search()的正确性。注意，当a[n-1] check(mid2)) … //移动right else … //移动left }

  下面是一个例题。 　　∎题目描述 　　“期末考试”，题目来源：https://www.lydsy.com/JudgeOnline/problem.php?id=4868 　　有n位同学，每位同学都参加了全部的m门课程的期末考试，都在焦急的等待成绩的公布。第i位同学希望在第ti天或之前得知所有课程的成绩。如果在第ti天，有至少一门课程的成绩没有公布，他就会等待最后公布成绩的课程公布成绩，每等待一天就会产生C不愉快度。对于第i门课程，按照原本的计划，会在第bi天公布成绩。有如下两种操作可以调整公布成绩的时间：1.将负责课程X的部分老师调整到课程Y，调整之后公布课程X成绩的时间推迟一天，公布课程Y成绩的时间提前一天；每次操作产生A不愉快度。2.增加一部分老师负责学科Z，这将导致学科Z的出成绩时间提前一天；每次操作产生B不愉快度。上面两种操作中的参数X,Y,Z均可任意指定，每种操作均可以执行多次，每次执行时都可以重新指定参数。现在希望你通过合理的操作，使得最后总的不愉快度之和最小，输出最小的不愉快度之和即可。 　　∎题解 　　不愉快度是一个下凹的函数，用三分法。代码略。