引子

首先我们来思考这样一个问题：

八枚金币中有一枚假币，假币的质量比真币轻，现给你一个不带砝码的天平，让你找出那枚假币，要求最坏情况下天平的操作次数尽量少，那么最少操作次数是多少？

这题其实是小学奥数题，很容易可以想到最少操作次数是 3 次，方法如下：

1. 将八枚金币均分成两份，分别放在天平两端，找出较轻的一份，假币一定在这一份中。

2. 将这一份的四枚金币均分成两份，分别放在天平两端，找出较轻的一份，假币一定在这一份中。

3. 将这一份的两枚金币均分成两份，分别放在天平两端，找出较轻的一枚，假币一定是这一枚。

容易发现，这三次操作十分相似，具体都可以概括为“均分检验，更新区间” ，如此重复，直至最后只剩一枚金币，那枚金币就是要找的假币。事实上，任何初始数量的金币中找一枚假币都可以用这个方法做。如果总金币数为  ，那么最少操作次数约为 次（最坏情况下）。

其实这种方法就是 二分法 ，是一种进行区间查找的算法，得益于其  的时间复杂度，且思想易懂，代码好写，常用于一般情况下题目中的区间查找。

概述

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

——OI Wiki

二分的本质在于 边界 。

当区间内有一个边界满足：它左边的所有点都有同一性质，而右边的点都有另一性质，那么这个区间就可以二分。

而因为大部分二分题目都与单调性相关，所以使用二分法之前大多需要对区间进行排序。

一般来讲，如果题目中出现了“最大值的最小”或“最小值的最大”一类的话，那么这道题大概率会用到二分。

以在一个单调递增的数组 a （左右端点分别为 l 和 r ）里求最大的不大于数 x 的那个数为例，先取区间中点 mid ，判断 mid 的值是否大于 x 。若大于，则更新 r ；若小于，则更新 l 。最后再对新区间重复以上操作，直至 l 等于 r 为止。此时 l 点即为要求的数。

二分最关键的一步在于检验 mid ，因此一个 check 函数一般是必不可少的，当然这还是取决于个人习惯和题目要求。

以下为一种二分模板的伪代码：

二分法可以粗略分为 整数二分 和 浮点数二分，分别运用于不同的场景。

整数二分

整数二分多用于区间查找以及求分界点。根据所需不同，又可以分为 lower_bound 和 upper_bound 两种，这两种方法模板不同且极易混淆，需特别注意。

• lower_bound

简单来讲， lower_bound 就是求分界点左边区间的最右点，即“最小值的最大”。

每次检验 mid 时判断其是否满足左边区间的性质。

若满足，则目标点一定在 mid 右侧，在区间 中；若不满足，则目标点一定在 mid 左侧，在区间 中。每次更新区间时，按上面的区间范围更新左或右端点。

例题：Luogu P1873 砍树

伐木工人 Mirko 需要砍 M 米长的木材。对 Mirko 来说这是很简单的工作，因为他有一个漂亮的新伐木机，可以如野火一般砍伐森林。不过，Mirko 只被允许砍伐一排树。

Mirko 的伐木机工作流程如下：Mirko 设置一个高度参数 H ，伐木机升起一个巨大的锯片到高度 H ，并锯掉所有树比 H 高的部分。Mirko 就得到树木被锯下的部分。例如，如果一排树的高度分别为 20,15,10,17 ，Mirko 把锯片升到 15 米的高度，切割后树木剩下的高度将是 15,15,10,15，而 Mirko 将从第 1 棵树得到 5 米，从第 4 棵树得到 2 米，共得到 7 米木材。

Mirko 非常关注生态保护，所以他不会砍掉过多的木材。所以他尽可能高地设定伐木机锯片。请帮助 Mirko 找到伐木机锯片的最大的整数高度 H，使得他能得到的木材至少为 M 米。换句话说，如果再升高 1 米，他将得不到 M 米木材。

这道题的边界很容易看出，超出 H 的部分应尽量少，但又要大于等于 M ，那么只需要将左端点设为 0（也可以设为所有树中的最低高度），将右端点设为最高高度，二分查找这个 H 就行了。

每次检验 mid 时遍历一遍数组，将多出 mid 的部分相加，总和与 M 比较，大于 M 则更新左端点，否则更新右端点。

二分总时间复杂度为  ，每次二分都要遍历一次数组，时间复杂度为  ，总时间复杂度为  ，足以过这道题。并且数组单调性与分界点无关，所以不需要排序。

另外还有非常关键的一点需注意：mid 应等于 l+r+1 以防止死循环。原因在代码部分会说。

以下为代码：

• upper_bound

与 lower_bound 相对应，upper_bound 是求右区间的左端点，即“最大值的最小”。

每次检验 mid 时判断其是否满足左边区间的性质。

若满足，则目标点一定在 mid 右侧，在区间 中；若不满足，则目标点一定在 mid 左侧，在区间  中。每次更新区间时，按上面的区间范围更新左或右端点。

例题：Luogu P2249 查找

输入 个不超过 的单调不减的（就是后面的数字不小于前面的数字）非负整数 ，然后进行  次询问。对于每次询问，给出一个整数 ，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 -1 。编号从 1 开始。

要在单调不减序列中查找一个数第一次出现的位置，也就是在序列中查找大于等于它的数的最小位置，而如果找到的数与给定的数不相等，说明序列中没有这个数。因为对一个数来讲，大于等于它的最小值一定为它本身。

那么思路就很明显了，将数组的左右端点视作二分的左右端点，二分查找大于等于它的数的最小位置，检验 mid 时将其作为下标对应的数与 q 作比较，若大于，则更新右端点，否则更新左端点。

一共进行 m 次二分，则总时间复杂度为 。

以下为代码：

浮点数二分

浮点数二分多用于数学运算中求更精确的数值（如求二次方根），并且在数学中也有使用二分法求函数零点的方法（详见人教版高中数学课本必修一）。相较于整数二分，浮点数二分较为简单且情况单一，但在一般比赛中不是很常见。

例题：Acwing 790

给定一个浮点数 n，求它的三次方根。

浮点数二分查找，检验 mid 时将其三次方根与 n 比较，大于则更新右端点，小于则更新左端点。

因为浮点数没有取整的烦恼，所以不用顾虑太多。不过考虑到精度的问题，一般浮点数二分只需要左右端点的差小于某个极小的数就可以了。一般来讲答案保留几位小数，就将差值边界的小数点再往左移一到两位就足够了。

或者也可以使用计数器，强制要求二分 100 次或 1000 次，因为二分复杂度毕竟是 ，这么多次精度也应该足够了。

以下为代码：

总结

总而言之，二分作为一种简单快捷易懂的基础算法，是每个OIer或信息学爱好者所须知的且能熟练掌握与应用的。 的时间复杂度与近似 的空间复杂度使得其在比赛中十分吃香。

拓展

c++中的算法库 <algorithm> 中有两个基于二分算法的查找函数，分别为 lower_bound 和 upper_bound 。

lower_bound 函数用于在指定单调非降区间（左闭右开）内查找不小于目标值的第一个元素；

upper_bound 函数用于在指定单调非降区间（左闭右开）内查找大于目标值的第一个元素。

二者的语法格式为：

函数返回一个迭代器，如果找到符合条件的元素则返回相对应的迭代器，否则返回 right 。

除二分以外，还有一种类似的算法为 三分法 ,用来查找单峰函数的最值。但在 NOI 的比赛中一般不会出现，所以不做过多深入。