二分

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

二分法

定义

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

过程

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

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

性质

时间复杂度

二分查找的最优时间复杂度为 $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
16

int binary_search(int start, int end, int key) {
  int ret = -1;  // 未搜索到数据返回-1下标
  int mid;
  while (start <= end) {
    mid = start + ((end - start) >> 1);  // 直接平均可能会溢出，所以用这个算法
    if (arr[mid] < key)
      start = mid + 1;
    else if (arr[mid] > key)
      end = mid - 1;
    else {  // 最后检测相等是因为多数搜索情况不是大于就是小于
      ret = mid;
      break;
    }
  }
  return ret;  // 单一出口
}

最大值最小化

注意，这里的有序是广义的有序，如果一个数组中的左侧或者右侧都满足某一种条件，而另一侧都不满足这种条件，也可以看作是一种有序（如果把满足条件看做 $1$，不满足看做 $0$，至少对于这个条件的这一维度是有序的）．换言之，二分搜索法可以用来查找满足某种条件的最大（最小）的值．

要求满足某种条件的最大值的最小可能情况（最大值最小化），首先的想法是从小到大枚举这个作为答案的「最大值」，然后去判断是否合法．若答案单调，就可以使用二分搜索法来更快地找到答案．因此，要想使用二分搜索法来解这种「最大值最小化」的题目，需要满足以下三个条件：

1. 答案在一个固定区间内；
2. 可能查找一个符合条件的值不是很容易，但是要求能比较容易地判断某个值是否是符合条件的；
3. 可行解对于区间满足一定的单调性．换言之，必须在整个区间内保持同一个方向：例如对所有 $x\le y$，$x$ 可行蕴含 $y$ 可行；或对所有 $x\ge y$，$x$ 可行蕴含 $y$ 可行．

当然，最小值最大化是同理的．

STL 的二分查找

C++ 标准库中实现了查找首个不小于给定值的元素的函数 std::lower_bound 和查找首个大于给定值的元素的函数 std::upper_bound，二者均定义于头文件 <algorithm> 中．

二者均采用二分实现，所以调用前必须保证元素有序．

bsearch

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

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

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

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

注意：bsearch 与上文的 lower_bound 和 upper_bound 有两点不同：

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

用 lower_bound 可以实现与 bsearch 完全相同的功能，所以可以使用 bsearch 通过的题目，直接改写成 lower_bound 同样可以实现．但是鉴于上述不同之处的第二点，例如，在序列 1、2、4、5、6 中查找 3，bsearch 实现 lower_bound 的功能会变得困难．

利用 bsearch 实现 lower_bound 和 upper_bound 时，可以利用其比较函数的参数约定：第一个参数指向待查元素，第二个参数指向待查数组中的元素．所以只要比较函数能得到数组首地址即可实现．

 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

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

// 查找首个不小于待查元素的元素的地址
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;
}

因为现在的 OI 选手很少写纯 C，并且此方法作用有限，所以不是重点．对于新手而言，建议使用 C++ 中的 std::lower_bound 和 std::upper_bound 函数．

二分答案

解题的时候往往会考虑枚举答案然后检验枚举的值是否正确．若满足单调性，则满足使用二分法的条件．把这里的枚举换成二分，就变成了「二分答案」．

 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/9/28 01:09:54，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：Ir1d, H-J-Granger, StudyingFather, c-forrest, 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, lychees, Marcythm, Peanut-Tang, Selflocking, shawlleyw, shuzhouliu, SukkaW, TH911, Tokur233, TOMWT-qwq, w-tianshui, zirnc
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用