二分

本页面将简要介绍二分查找、二分答案，以及由二分法衍生的三分法．

二分查找

二分查找（binary search），也称折半搜索（half-interval search）、对数搜索（logarithmic search），是用来在一个有序序列中查找某一元素的算法．

过程

以在一个升序数组中查找一个数为例．

它每次访问数组当前部分的中间元素，如果中间元素刚好是要找的，就结束搜索过程；如果中间元素小于所查找的值，那么左侧的元素都不大于中间元素，不可能有所查找的元素，只需到右侧查找；如果中间元素大于所查找的值同理，只需到左侧查找．

具体地，设数组 $a$ 下标从 $1$ 开始，长度为 $n$，要查找数 $x$ 在哪个位置．令 $l,r$ 表示当前只考虑数组中下标 $i$ 满足 $l\le i\le r$ 的数．一开始时，令 $l\leftarrow 1$，$r\leftarrow n$．每次访问中间元素 $a_{\mathit{\text{mid}}}$，其中 $\mathit{\text{mid}}=\lfloor {\displaystyle \frac{l+r}{2}}\rfloor$，然后分情况讨论：

• 若 ，由于数组升序，下标小于等于 $\mathit{\text{mid}}$ 的数一定都比 $x$ 小，因此一定不用查找这些数，只需要查找下标大于 $\mathit{\text{mid}}$ 的数就可以了，也就是令 $l\leftarrow \mathit{\text{mid}}+1$，$r$ 不变．
• 若 ，由于数组升序，下标大于等于 $\mathit{\text{mid}}$ 的数一定都比 $x$ 大，因此一定不用查找这些数，只需要查找下标小于 $\mathit{\text{mid}}$ 的数就可以了，也就是令 $l$ 不变，$r\leftarrow \mathit{\text{mid}}-1$．
• 若 $a_{\mathit{\text{mid}}}=x$，我们就找到了数 $x$ 的位置，算法结束．

如果直到考虑范围为空，即 时都没有找到数 $x$ 的位置，就说明 $x$ 不在数组 $a$ 中．

性质

时间复杂度

二分查找的最优时间复杂度为 $O(1)$．

二分查找的平均时间复杂度和最坏时间复杂度均为 $O(\log n)$．因为在二分查找过程中，算法每次都把待查找的区间减半，所以对于一个长度为 $n$ 的数组，至多会进行 $O(\log n)$ 次和目标元素的比较．

空间复杂度

迭代版本的二分查找的空间复杂度为 $O(1)$．

递归（无尾调用消除）版本的二分查找的空间复杂度为 $O(\log n)$．

实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

int binary_search(int x, int l = 1, int r = n) {  // 在升序数组中查找数 x 的下标
  int ret = -1;                                   // 未找到时返回 -1
  while (l <= r) {
    int mid = (l + r) >> 1;  // l + r 可能溢出，详见下方 Note
    if (a[mid] < x)
      l = mid + 1;
    else if (a[mid] > x)
      r = mid - 1;
    else {  // 最后检测相等是因为多数搜索情况不是大于就是小于
      ret = mid;
      break;
    }
  }
  return ret;
}

bsearch

bsearch 函数为 C 标准库实现的二分查找，定义在 <stdlib.h> 中．在 C++ 标准库里，该函数定义在 <cstdlib> 中．qsort 和 bsearch 是 C 语言标准库中仅有的两个算法类函数．

bsearch 函数相比 qsort（排序相关 STL）的四个参数，在最左边增加了参数「待查元素的地址」．之所以按照地址的形式传入，是为了方便直接套用与 qsort 相同的比较函数，从而实现排序后的立即查找．因此这个参数不能直接传入具体值，而是要先将待查值用一个变量存储，再传入该变量地址．

于是 bsearch 函数总共有五个参数：待查元素的地址、数组首地址、元素个数、元素大小、比较规则．比较规则仍然通过指定比较函数实现，详见 排序相关 STL．

bsearch 函数的返回值是查找到的元素的地址，返回类型为 void *．

注意：bsearch 与下文将要介绍的 std::lower_bound 和 std::upper_bound 有两点不同：

• 当有多个符合条件的元素时，返回其中哪一个未指定．
• 当查找不到相应的元素时，会返回 NULL．

用 lower_bound 可以实现与 bsearch 近乎相同的功能（只需要特别判断查找不到元素的情况即可做到完全相同），所以可以使用 bsearch 通过的题目，直接改写成 lower_bound 同样可以实现．

二分答案

二分答案是利用问题答案的广义有序性质（通常也被称为单调性），通过类似二分查找的方式快速求出答案的算法．

如果没有特殊说明，二分答案通常代指整数范围的二分答案，即已知答案必定是整数．

能够利用二分答案的问题通常形如「求满足条件 $P$ 的最大（小）值」，并具有如下性质：

1. 如果给出任意数 $x$，容易判断 $x$ 是否满足条件；
2. 问题的答案可以划定一个粗略的上下界，即可以确定 $L$ 和 $R$ 使得若答案 $x$ 存在，则 $x$ 必然满足 $L\le x\le R$；
3. 划定的粗略的上下界范围很大，一个个枚举并且判断会超时；
4. 条件 $P$ 具有广义的有序性质．

假设存在一个函数 $f(x)$，当且仅当 $x$ 满足条件 $P$ 时 $f(x)=1$，否则 $f(x)=0$，则可以用下列方式定义条件 $P$ 的广义有序性质：

• 若对于任意的 ，$f(i)\le f(j)$，即 $f(x)$ 单调不减．将 $i=L,\dots ,R$ 的 $f(i)$ 写成一个 01 序列时形如 00...011...1．此时二分答案可以求出满足条件 $P$ 的 最小值．

• 若对于任意的 ，$f(i)\ge f(j)$，即 $f(x)$ 单调不增．对应的 01 序列形如 11...100...0．此时二分答案可以求出满足条件 $P$ 的 最大值．

换言之，第一种有序性质是指：如果知道 $x$ 满足条件 $P$，则所有比 $x$ 大的数一定都满足条件 $P$．二分答案可以求出符合「比它小的数都不满足条件 $P$，它和比它大的数都满足条件 $P$」这一描述的 $x$．

而第二种有序性质是指：如果知道 $x$ 满足条件 $P$，则所有比 $x$ 小的数一定都满足条件 $P$．二分答案可以求出符合「它和比它小的数都满足条件 $P$，比它大的数都不满足条件 $P$」这一描述的 $x$．

过程

以利用二分答案求最小值为例（此时算法要求问题满足上文所述的第一种有序性质）．设答案的粗略上下界为 $L$ 和 $R$．

令 $l,r$ 表示当前可以确定答案 $x$ 一定满足 $l\le x\le r$．和二分查找类似，一开始时，令 $l\leftarrow L$，$r\leftarrow R$．每次我们判断 $\mathit{\text{mid}}=\lfloor {\displaystyle \frac{l+r}{2}}\rfloor$ 是否满足条件 $P$，然后分情况讨论：

• 如果 $\mathit{\text{mid}}$ 不满足条件（即 $f(\mathit{\text{mid}})$ 为 $0$），根据问题的有序性质，此时小于等于 $\mathit{\text{mid}}$ 的所有数都不满足条件，都无需考虑，因此令 $l\leftarrow \mathit{\text{mid}}+1$，$r$ 不变．
• 如果 $\mathit{\text{mid}}$ 满足条件（即 $f(\mathit{\text{mid}})$ 为 $1$），根据问题的有序性质，此时大于等于 $\mathit{\text{mid}}$ 的所有数都满足条件，但是因为题目要求最小值，所以所有大于 $\mathit{\text{mid}}$ 的数都没必要考虑了，只考虑小于等于 $\mathit{\text{mid}}$ 的数就可以了．此时令 $r\leftarrow \mathit{\text{mid}}$，$l$ 不变．

当答案范围满足 $l=r$（即不再满足 ）时，算法结束．此时 $l$ 或 $r$ 为答案．

需要注意的是：若上下界内答案不存在（即通常所说的无解），每次查询 $f(\mathit{\text{mid}})$ 都会返回 $0$，因此算法结束后 $l=r=R$，且 $f(l)=0$．因此如果需要判断无解，额外检查 $f(l)$ 是否等于 $0$ 即可．

和二分查找类似，算法每次都把待搜索的区间减半，因此算法的时间复杂度为 $O(M\log (R-L+1))$，其中 $M$ 为每次判断 $\mathit{\text{mid}}$ 是否满足条件 $P$ 的时间复杂度．

实现

根据上面的算法描述，可以给出如下实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

// 求 [L, R] 内满足条件 P 的最小整数 x，要求 L <= R
// 条件 P 需要满足第一种有序性质，即 f(x) 单调不减
// 在代码实现中，通常 check(x) = f(x)
// 若区间内无解，返回 -1
int binary_search_min(int L, int R) {
  if (L > R) return -1;
  int l = L, r = R;
  while (l < r) {
    int mid = (l + r) >> 1;
    if (check(mid))  // f(mid) = 1，满足条件 P
      r = mid;       // 答案在 [l, mid]
    else
      l = mid + 1;  // 答案在 [mid + 1, r]
  }
  // 此时 l == r
  if (!check(l)) return -1;  // 无解判断
  return l;
}

使用 -1 表示无解时，需要保证它不会与合法答案混淆．

实现细节

在查看题解时，我们可能会看到另一种实现方式：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

// 求 [L, R] 内满足 check(x) 的最小整数 x
// 要求 check 在 [L, R] 上单调不减
// 若区间为空或区间内无解，返回 -1
int binary_search_min(int L, int R) {
  if (L > R) return -1;
  int l = L, r = R;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (check(mid))
      r = mid - 1;
    else
      l = mid + 1;
  }

  if (l > R) return -1;
  return l;
}

这两种写法求出的答案是相同的，但维护的循环不变量不同．

为什么两种写法都能找到最小可行值？

先假设 $[L,R]$ 非空，且区间内存在答案，记最小的满足条件 $P$ 的数为 $\mathit{\text{ans}}$．由 $f$ 单调不减的性质，在原区间 $[L,R]$ 内有

l < r 的写法将答案保留在闭区间内．

它维护的不变量是

$$l\le \mathit{\text{ans}}\le r.$$

每次取 $\mathit{\text{mid}}=\lfloor {\displaystyle \frac{l+r}{2}}\rfloor$．若 $f(\mathit{\text{mid}})=1$，则 $\mathit{\text{ans}}\le \mathit{\text{mid}}$，令 $r\leftarrow \mathit{\text{mid}}$；若 $f(\mathit{\text{mid}})=0$，则 ，令 $l\leftarrow \mathit{\text{mid}}+1$．两种更新都保持不变量．

当 时，有 ，因此每次迭代都会使区间严格缩小．循环结束时 $l=r$，由不变量可知 $\mathit{\text{ans}}=l$．

l <= r 的写法排除已经确定的部分，答案可能位于右边界的后一位．

它维护的不变量是：在原区间 $[L,R]$ 内，所有 都满足 $f(x)=0$，所有 都满足 $f(x)=1$．在答案存在的前提下，这意味着

$$l\le \mathit{\text{ans}}\le r+1.$$

若 $f(\mathit{\text{mid}})=1$，则原区间内所有 $x\ge \mathit{\text{mid}}$ 都满足 $f(x)=1$，可以令 $r\leftarrow \mathit{\text{mid}}-1$；若 $f(\mathit{\text{mid}})=0$，则原区间内所有 $x\le \mathit{\text{mid}}$ 都满足 $f(x)=0$，可以令 $l\leftarrow \mathit{\text{mid}}+1$．

每次迭代都会从待搜索区间中排除至少一个整数，因此循环最终会结束．

而循环执行时，有 $l\le \mathit{\text{mid}}\le r$．若执行 $r\leftarrow \mathit{\text{mid}}-1$，则新的右边界满足 $r\ge l-1$；若执行 $l\leftarrow \mathit{\text{mid}}+1$，则新的左边界满足 $l\le r+1$．因此，无论采用哪种更新，更新后都有 $l\le r+1$．循环在 时结束，结合整数边界的性质可知，此时必有 $l=r+1$．再由答案位置不变量 $l\le \mathit{\text{ans}}\le r+1$，得到 $\mathit{\text{ans}}=l$．

这里需要注意：待搜索区间 $[l,r]$ 不一定始终包含答案．例如，若本轮恰好取到 $\mathit{\text{mid}}=\mathit{\text{ans}}$，执行 $r\leftarrow \mathit{\text{mid}}-1$ 后，就有 $\mathit{\text{ans}}=r+1$．此时答案虽然已经不在 $[l,r]$ 内，却仍然满足不变量 $l\le \mathit{\text{ans}}\le r+1$，因此不会影响上述正确性证明．

无解时，两种写法的终止位置不同．

对于 l <= r 的写法，若循环结束后有 $l\le R$，由于左边界始终满足 $l\ge L$，可知 $l$ 位于原区间内．再由 $l=r+1$ 以及「原区间内所有 都满足 $f(x)=1$」这一不变量，可知 $f(l)=1$，因此不必再次调用 check(l)．

若无解，则最终有 $l=R+1$，已经超出原搜索区间．由于我们只要求 check 在 $[L,R]$ 内可用，因此应先检查 l > R，不能直接调用 check(l) 来判断是否有解．

而对于 l < r 的写法，回顾前面的描述可以得知，如果在区间内无解，则最终 $l=r=R$．此时需要额外判断 check(l) 是否为 $0$ 来区别到底是答案为 $R$ 还是区间内无解．

综上，在 $L\le R$ 且 $f$ 在 $[L,R]$ 上单调不减的前提下，两种写法都能在有限次迭代后结束．若区间内存在可行值，它们最终都得到 $l=\mathit{\text{ans}}$，返回区间内满足条件的最小整数；若区间内无解，l < r 的写法通过结束后的 check(l) 判定无解，l <= r 的写法通过结束后的 l > R 判定无解，两者均返回约定的无解标记．对于 的空区间，两段代码都会在进入循环前直接返回无解标记．因此，两种实现虽然维护的循环不变量和终止位置不同，但都能正确完成所要求的最小可行值查询，并得到相同的返回结果．

这两种写法说明，二分实现的正确性取决于边界含义、循环不变量、循环条件和更新规则之间的配合．仅根据区间端点是否包含在内，或者循环使用 l < r 还是 l <= r，还不足以判断一种写法是否正确．

证明一种写法正确，需要确认：

1. 初始化满足循环不变量．
2. 每次更新都保持不变量，并使待搜索区间中的整数个数严格减少，从而保证循环最终结束．
3. 循环结束时，能够由不变量和终止条件确定返回值就是答案；若允许无解，还需说明如何识别无解情况．

在讨论实现方式时，需要特别区分「尚待搜索的区间」与「保证包含最终答案的区间」：由于边界条件不同，二者不一定相同，不能统一要求答案始终位于待搜索区间内．

下面列出几种常见写法．均假设 $L\le R$、问题满足第一种有序性质，且最小可行值 $\mathit{\text{ans}}$ 存在．答案的位置以「答案位置不变量」一列为准．

写法	初始 $l,r$	循环条件	$\mathit{\text{mid}}$	$f(\mathit{\text{mid}})=1$ 时	$f(\mathit{\text{mid}})=0$ 时	答案位置不变量	结束时	返回
闭区间 $[l,r]$，排除已判定部分	$l=L,r=R$	$l\le r$	$\lfloor {\displaystyle \frac{l+r}{2}}\rfloor$	$r\leftarrow \mathit{\text{mid}}-1$	$l\leftarrow \mathit{\text{mid}}+1$	$l\le \mathit{\text{ans}}\le r+1$	$l=r+1$	$l$
闭区间 $[l,r]$，保留答案	$l=L,r=R$		$\lfloor {\displaystyle \frac{l+r}{2}}\rfloor$	$r\leftarrow \mathit{\text{mid}}$	$l\leftarrow \mathit{\text{mid}}+1$	$l\le \mathit{\text{ans}}\le r$	$l=r$	$l$
左闭右开区间 $[l,r)$，排除已判定部分	$l=L,r=R+1$		$\lfloor {\displaystyle \frac{l+r}{2}}\rfloor$	$r\leftarrow \mathit{\text{mid}}$	$l\leftarrow \mathit{\text{mid}}+1$	$l\le \mathit{\text{ans}}\le r$	$l=r$	$l$
左开右闭区间 $(l,r]$，保留答案	$l=L-1,r=R$		$\lfloor {\displaystyle \frac{l+r}{2}}\rfloor$	$r\leftarrow \mathit{\text{mid}}$	$l\leftarrow \mathit{\text{mid}}$		$l+1=r$	$r$
开区间 $(l,r)$，维护两侧边界	$l=L-1,r=R+1$		$\lfloor {\displaystyle \frac{l+r}{2}}\rfloor$	$r\leftarrow \mathit{\text{mid}}$	$l\leftarrow \mathit{\text{mid}}$		$l+1=r$	$r$

表中还有几点需要说明：

• 第 3 行的 $[l,r)$ 是待搜索区间，但答案可能恰好等于 $r$．
• 第 4 行将答案保留在 $(l,r]$ 内，依赖初始右边界 $R$ 满足 $f(R)=1$．循环执行时 $r-l\ge 2$，因此第 4、5 行的中点改用上取整也正确．
• 第 5 行中的 $(l,r)$ 表示两个边界之间尚待判断的位置．可以将初始的 $L-1$ 视为值为 0 的虚拟哨兵，将 $R+1$ 视为值为 1 的虚拟哨兵．循环只在原区间内调用判定函数，不需要实际计算哨兵处的函数值．
• 若要处理无解情况：第 1、3、5 行可以通过返回值是否为 $R+1$ 判断；第 2 行需要检查 $f(l)$；第 4 行需要先检查 $f(R)$．

最大值最小化与最小值最大化

最大值最小化与最小值最大化问题是典型的能够应用二分答案算法解决的问题．

以最大值最小化问题为例．通常每个方案对应一个需要考虑的集合 $S$．若要求在所有方案中，使得方案对应集合 $S$ 中数最大值最小化，可以转化问题为：求最小的 $k$，使得存在方案满足 $max(S)\le k$．

而这个问题具备广义有序性质：若存在方案满足 $max(S)\le k$，则对于 $i\ge k$，该方案也满足 $max(S)\le i$．因此对于 $i\ge k$，存在方案满足 $max(S)\le i$，同样符合题目条件．于是可以通过二分答案解决．最小值最大化问题同理．

STL 的二分答案

std::lower_bound 与 std::upper_bound

C++ 标准库中实现了：

• 查找首个不小于给定值的元素的函数 std::lower_bound．
• 查找首个大于给定值的元素的函数 std::upper_bound．

二者均采用二分实现，所以调用前必须保证元素有序（注意这里的有序是指基于下面的比较函数而言的，不一定是数学意义上的有序），这样二者的问题才满足广义的有序性质（即对于 std::lower_bound，若 $a_i$ 不小于给定值时，$i$ 之后的数同样不小于给定值；对于 std::upper_bound，若 $a_i$ 大于给定值时，$i$ 之后的数同样大于给定值）．

std::lower_bound 和 std::upper_bound 均有四个参数，分别是：

• first：序列的起始 迭代器，指向序列的首个元素．
• last：序列的终止迭代器，指向序列的最后一个元素的 后一位置．换言之，如果 last 是双向迭代器，则 --last 指向的是序列的最后一个元素．
• value：给定值．
• comp（可选）：比较函数，参考 sort 函数的书写方式．需要注意 std::lower_bound 以 comp(元素, value) 的形式调用，而 std::upper_bound 以 comp(value, 元素) 的形式调用．

二者的返回值均为满足条件的元素的迭代器，类型同传入的一致．也就是说，如果传入数组指针，则返回满足条件的元素对应的数组指针．如果找不到满足条件的元素，返回 last．

二者均定义于头文件 <algorithm> 中．

 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
29

int A[100005];  // 示例全局数组

// compare 比较两个 int 指针指向的值：*p1 > *p2 返回正数，相等返回
// 0，小于返回负数
int compare(const void*, const void*);

// 查找首个不小于待查元素的元素的地址
int lower(const void* p1, const void* p2) {
  int* a = (int*)p1;
  int* b = (int*)p2;
  if ((b == A || compare(a, b - 1) > 0) && compare(a, b) > 0)
    return 1;
  else if (b != A && compare(a, b - 1) <= 0)
    return -1;  // 用到地址的减法，因此必须指定元素类型
  else
    return 0;
}

// 查找首个大于待查元素的元素的地址
int upper(const void* p1, const void* p2) {
  int* a = (int*)p1;
  int* b = (int*)p2;
  if ((b == A || compare(a, b - 1) >= 0) && compare(a, b) >= 0)
    return 1;
  else if (b != A && compare(a, b - 1) < 0)
    return -1;  // 用到地址的减法，因此必须指定元素类型
  else
    return 0;
}

std::partition_point

C++11 引入了 std::partition_point．其作用是在一个已分区的序列中，通过二分答案快速定位「分区点」．

std::partition_point 有三个参数，分别是：

• first、last：同上．
• p：一个一元 谓词．这是一个可调用对象，支持传入一个参数 $v$，并返回一个布尔值表示 $v$ 是否符合分区条件．

设传入的序列为 $a$，则该函数返回第一个不满足分区条件的元素的迭代器，即返回迭代器指向下标 $x$ 最小的满足 $p(a_x)$ 等于 false 的元素．

该序列需要已分区，即需要满足上文所述第二种广义有序性质．换言之，将序列中每个元素 $v$ 的 $p(v)$ 的结果列成一个 01 序列，则该序列形如 11...100...0，该函数返回第一个 $0$ 对应位置的迭代器．

实数二分答案

实数二分答案，也称浮点二分，是二分答案在答案为实数时的一种形式．

与整数二分答案不同，实数二分答案通常不要求求出精确的答案，而是求一个满足给定精度要求的实数近似值．

过程

以求最小值为例．设答案的粗略上下界为 $L$ 和 $R$．记 $l,r$ 表示当前可以确定答案 $x$ 一定满足 $l\le x\le r$．一开始时，令 $l\leftarrow L$，$r\leftarrow R$．每次取 $\mathit{\text{mid}}={\displaystyle \frac{l+r}{2}}$（注意，这里是实数运算），判断 $\mathit{\text{mid}}$ 是否满足条件 $P$：

• 若 $\mathit{\text{mid}}$ 满足条件，与整数情形类似，令 $r\leftarrow \mathit{\text{mid}}$，$l$ 不变．
• 若 $\mathit{\text{mid}}$ 不满足条件，与整数情形类似，令 $l\leftarrow \mathit{\text{mid}}$，$r$ 不变．

需要注意的是，与整数二分答案不同，实数二分答案不能通过 mid + 1 或 mid - 1 缩小区间，因为实数域中不存在相邻元素；只能令边界等于 $\mathit{\text{mid}}$，依赖区间长度不断减半来逼近答案．

当区间长度 $r-l$ 不超过给定精度 $\mathit{\text{eps}}$，或达到预设的迭代次数时，算法结束．此时 $l$、$r$ 或 ${\displaystyle \frac{l+r}{2}}$ 均可作为答案的近似值（若要求最终返回值满足条件 $P$，应返回 $r$）．求最大值时，只需将上述两种情况的方向反过来：若 $\mathit{\text{mid}}$ 满足条件，则令 $l\leftarrow \mathit{\text{mid}}$；否则令 $r\leftarrow \mathit{\text{mid}}$（相应地，若要求最终返回值满足条件 $P$，应返回 $l$）．

若采用 while (r - l > eps)，实数二分答案的时间复杂度为 $O(M\log ((R-L)/\mathit{\text{eps}}))$．若采用固定迭代次数 $k$，则时间复杂度为 $O(Mk)$．其中 $M$ 为每次判断 $\mathit{\text{mid}}$ 是否满足条件 $P$ 的时间复杂度．由于实数运算存在浮点误差，实际实现中通常不直接判断 $l=r$，而是判断 ，或直接循环固定次数，例如 $60$ 至 $100$ 次，以避免死循环并保证精度．

实现

 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

double binary_search_iter(double L, double R) {  // 固定迭代次数实现
  double l = L, r = R;
  for (int i = 0; i < 100; ++i) {
    double mid = (l + r) / 2;
    if (check(mid))
      r = mid;
    else
      l = mid;
  }
  return r;
}

const double eps = 1e-7;  // 精度要求，通常取题目要求精度的 1/100 或更小

double binary_search_eps(double L, double R) {  // eps 实现
  double l = L, r = R;
  while (r - l > eps) {
    double mid = (l + r) / 2;
    if (check(mid))
      r = mid;
    else
      l = mid;
  }
  return r;
}

例题

 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
29
30
31
32
33

#include <iostream>
using namespace std;

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 = 0, r = 1e9 + 1;   // 因为是左闭右开的，所以 10^9 要加 1
                            // 保持 check(l) 为真、check(r) 为假
  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;
}

三分法

引入

二分法可以用于近似求出函数的零点．如果需要求出单峰函数的极值点，通常需要使用三分法（ternary search）．

本节采用如下严格单峰约定：对于定义在 $[l,r]$ 上的函数 $f(x)$，如果存在 $x^{\ast }\in [l,r]$，使得 $f(x)$ 在 $[l,x^{\ast }]$ 上严格单调递增，在 $[x^{\ast },r]$ 上严格单调递减，就称 $f(x)$ 为单峰函数（unimodal function）．这里两个区间均包含 $x^{\ast }$，因此 $x^{\ast }$ 是唯一的最大值点，而 $f(x^{\ast })$ 是最大值．

为什么不通过求导函数的零点来求极值点？

首先，单峰并不保证导数零点唯一，导数为零的点也未必是最大值点．例如

$f^{\prime }(x)$ 的零点为 $x=1$ 与 $x=3$，而 $f(x)$ 的最大值在不可导的 $x=2$ 处取得．

其次，对于一些函数，求导的过程和结果比较复杂，甚至无法写成 $y=f(x)$ 的形式．

最后，某些题中需要求极值点的单峰函数并非一个单独的函数，而是多个函数进行特殊运算得到的函数（如求多个单调性不完全相同的一次函数的最小值的最大值）．此时函数的导函数可能是分段函数，且在函数某些点上可能不可导．

过程

三分法与二分法的基本思想类似，但每次操作需在当前区间 $[l,r]$（下图中两个橙点之间）内任取两点 （下图中的两个蓝点）．如下图所示，如果 ，则在 $[l,\mathit{\text{lmid}})$（下图中的红色部分）中函数必然单调递增，最大值点（下图中的绿点）必然不在这一区间内，可舍去这一区间；但是，无法排除最大值点在 $\mathit{\text{rmid}}$ 右侧的可能性，所以无法舍去更多区间．反之亦然．

三分法的正确性并不依赖于 $\mathit{\text{lmid}}$ 和 $\mathit{\text{rmid}}$ 的具体选择，只需保证它们是区间内的两个不同点，通常可以取两个三等分点．但是，它们的选择会影响三分法的效率．每次操作都会舍去两侧区间中的一个，因此也可以取靠近中点的两个分点，以增大能舍去的区间．若取 $\mathit{\text{mid}}\pm \delta$，其中 足够小，此时比较函数值相当于判断近似导数 ${\displaystyle \frac{f(\mathit{\text{mid}}+\delta )-f(\mathit{\text{mid}}-\delta )}{2\delta }}$ 的符号．由于算法竞赛中遇到的函数往往都有良好的光滑性，所以我们可以基于此来粗略判定极值点位于 $\mathit{\text{mid}}$ 哪一侧，从而达到接近二分法的效率．

实现

伪代码如下：

优化：黄金分割法

如果单次调用 $f(x)$ 的成本很高，需要进一步减少 $f(x)$ 的调用次数，可以通过黄金分割法（golden-section search）进一步改进三分法的常数．这也是华罗庚提出的优选法的重要内容．

三分法中，每轮迭代需要两次函数调用，且单轮迭代后区间长度至多缩短到原来的 $1/2$．这意味着，要达到精度 $\epsilon$，至少需要

$$2{\log }_2\frac{r-l}{\epsilon }$$

次函数调用．这是三分法能够取得的最好的结果．如果选取其他分点，例如三等分点，那么调用次数会进一步增加，因为单轮迭代后区间缩短得更慢．

黄金分割法的改进思路是，复用前文已经计算过的分点．这样，除了第一轮迭代需要两次函数调用外，其余轮次的迭代只需要一次函数调用．设黄金分割比为

$$\varphi =\frac{\sqrt{5}-1}{2}\approx 0.618.$$

每轮迭代时，选取的分点是左右两个黄金分割点：

$$m^l=\varphi l+(1-\varphi )r,m^r=(1-\varphi )l+\varphi r.$$

黄金分割点分割线段具有自相似结构．也就是说，$m^l$ 是线段 $[l,r]$ 的左黄金分割点，也是线段 $[l,m^r]$ 的右黄金分割点．这样选取分点的好处是，第 轮迭代选取的分点中，一定有一个分点是之前已经计算过的，可以直接复用之前的计算结果．

这样选取分点后，要达到精度 $\epsilon$，只需要

$$1+{\log }_{{\varphi }^{-1}}\frac{r-l}{\epsilon }\approx 1+1.44{\log }_2\frac{r-l}{\epsilon }$$

次函数调用．渐近意义上，函数的调用次数更少．

伪代码如下：

例题

 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
29
30

#include <cmath>
#include <iomanip>
#include <iostream>
using namespace std;

constexpr double eps = 1e-7;
int N;
double l, r, A[20], lmid, rmid;

double f(double x) {
  double res = (double)0;
  for (int i = N; i >= 0; i--) res += A[i] * pow(x, i);
  return res;
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> N >> l >> r;
  for (int i = N; i >= 0; i--) cin >> A[i];
  while (r - l > eps) {
    lmid = l + (r - l) / 3;
    rmid = r - (r - l) / 3;
    if (f(lmid) > f(rmid))
      r = rmid;
    else
      l = lmid;
  }
  cout << fixed << setprecision(6) << (l + r) / 2;
  return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

eps = 1e-7
n, l, r = map(float, input().split())
a = tuple(map(float, input().split()))[::-1]


def f(x):
    return sum(x**i * j for i, j in enumerate(a))


while r - l > eps:
    lmid = l + (r - l) / 3
    rmid = r - (r - l) / 3
    if f(lmid) > f(rmid):
        r = rmid
    else:
        l = lmid
print(f"{(l + r) / 2:.6f}")

习题

• UVa 1476 - Error Curves
• UVa 10385 - Duathlon
• UOJ 162 -【清华集训 2015】灯泡测试
• 洛谷 P7579 -「RdOI R2」称重（weigh）

分数规划

参见：分数规划

分数规划通常描述为下列问题：每个物品有两个属性 $c_i$，$d_i$，要求通过某种方式选出若干个，使得 ${\displaystyle \frac{\sum c_i}{\sum d_i}}$ 最大或最小．

经典的例子有最优比率环、最优比率生成树等等．

分数规划可以用二分法来解决．

参考资料与注释

• Ternary search - Wikipedia
• Golden-section search - Wikipedia
• Ternary search - CP Algorithms

本页面最近更新：2026/10/3 23:46:49，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：Ir1d, c-forrest, H-J-Granger, StudyingFather, NachtgeistW, sshwy, yusancky, countercurrent-time, Enter-tainer, Tiphereth-A, AngelKitty, cbw2007, CCXXXI, cjsoft, diauweb, Early0v0, ezoixx130, GekkaSaori, Henry-ZHR, Konano, ksyx, LovelyBuggies, Makkiy, mgt, minghu6, P-Y-Y, PotassiumWings, SamZhangQingChuan, Suyun514, weiyong1024, Xeonacid, billchenchina, FinParker, flylai, gavinliu266, GavinZhengOI, Gesrua, Great-designer, HanwGeek, HeRaNO, hhc0001, i-yyi, iamtwz, inclyc, kxccc, LeiJinpeng, leoleoasd, liangbob2023, lychees, Marcythm, Peanut-Tang, Selflocking, shawlleyw, shuzhouliu, SukkaW, TH911, Tokur233, TOMWT-qwq, w-tianshui, zirnc
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用