Ⅰ 二分法、二分查找(Binary Search)
一、 工作原理
二分查找是一种在O(log_2 n)范围内在有序数列上查找特定数的算法，具体如下工作：
假设你所找的数为x，起始可判断x在区间[1,n]中，每次取区间左端点和右端点的中间值，并判断其与x的大小关系，此处以升序为例，若Mid值比x大，则将区间[L,R]更新为[L,Mid]，也就是我们能够判断x一定在区间[L,Mid]内；若Mid比x小，则x在区间[Mid,R]内。
二、时间复杂度
容易知道，由于每次选择一半的区间，最多查找log_2n次就能找到特定值，那么其最坏复杂度就是O(log_2n)。
三、STL的二分查找
与<algorithm>库中有lower_bound和upper_bound两个二分查找的函数，具体作用可自行百度。
四、最大值最小化和二分答案
这类问题都是建立在答案的单调性上的。
Ⅱ 三分法
一、工作原理
三分法能够在单峰函数中在O(log_{\frac{3}{2}}n)范围内查找极值。
以下转载自OI Wiki
-
如果
lmid（图中较左的蓝点）和rmid（图中较右的蓝点）在最值的同侧（图中最值在两蓝点的右侧）：由函数为单峰函数可知二者中较大（小）的自变量值离最值的自变量值更近，舍去较远的点对应的区间（图中红色的区间）。 -
如果函数的最值在
lmid和rmid之间（图中两蓝点之间的区间）：由于最值在二者中间，可以舍去两侧的区间。但为和上一分类保持一致性，舍去较远的点对应的区间（图中红色的区间）。
二、时间复杂度
同二分查找一般，三分法每次舍弃1/3的区间，那么最坏复杂度分析就是O(log_{\frac{3}{2}}n)。
Ⅲ 分数规划
一、定义
给定若干件物品，每个物品有两个属性，问选出若干个物品其第一个属性之和与第二个属性之和的比最大(或最小)是多少。
例如：给定n个物品，每个物品有两个属性a_i和b_i，选出物品集合E，使\frac{\Sigma_{i\in E}a[i]}{\Sigma_{j\in E}b[j]}最大，同时可以给定若干限制条件。
二、Dinkelbach定理
设最优解E^{*}对应的t为t^{*}，则有\frac{\Sigma_{i\in E^{*}}a[i]}{\Sigma_{j\in E^{*}}b[j]}= t^{*}。
则\Sigma_{i\in E^{*}}a[i]-t^{*} *b[i]= 0
构造函数g(t)=\Sigma_{i\in E} a[i]-t*b[i]（g(t)为t情况下的最大或最小解）。
那么有g(t)=0\Leftrightarrow t=t^{*}
三、二分法
若我们加一个限制条件，选择的物品数量应大于k个。
考虑最终答案为t，那么一定有\frac{\Sigma_{i\in E}a[i]}{\Sigma_{j\in E}b[j]}= t。
同乘、移项得：\Sigma_{i\in E}a[i]-t*\Sigma_{j\in E}b[j]= 0。
合并可得：\Sigma_{i\in E}a[i]-t*b[i]= 0
我们令c[i]=a[i]-t*b[i]，容易知道\Sigma_{i\in E} c[i]=\Sigma_{i\in E}a[i]-t*b[i]关于t单调。
所以我们可以二分t并每次构造c，从大到小sort后取前k个判断其与的大小关系，来确定下一个二分的区间。
总复杂度nlog_2^2n。