十个二分, 九个错!
引言
在计算机科学中, 二分搜索, 也称为半区间搜索, 对数搜索, 或二分切分, 是一种搜索算法, 用于查找目标值在已排序数组中的位置. 二分查找将目标值与数组的中间元素进行比较. 如果它们不相等, 则消除目标不能位于的一半, 并继续搜索剩余的一半, 再次将中间元素与目标值进行比较, 并重复此操作, 直到找到目标值. 如果搜索以剩余一半为空而结束, 则目标不在数组中.
在最坏的情况下, 二分搜索以对数时间运行, 时间复杂度为 $O(\log n)$, 其中 $n$ 是数组中元素的数量. 除小数组外, 二分查找比线性查找快. 但是, 必须首先对数组进行排序才能应用二进制搜索. 有专门为快速搜索而设计的数据结构, 例如哈希表, 可以比二分搜索更有效地进行搜索. 但是, 二分查找可用于解决更广泛的问题, 例如查找数组中相对于目标的下一个最小或下一个最大元素, 即使它不存在于数组中.
二分法的历史
对项目列表进行排序以加快搜索速度的想法可以追溯到古代. 已知最早的例子是来自巴比伦的 Inakibit-Anu 平板电脑, 其历史可追溯至公元前 200 年. 该表格包含大约 500 个六十进制数字, 它们的倒数按字典顺序排序, 这使得搜索特定条目变得更加容易. 此外, 在爱琴海群岛上还发现了几个按首字母排序的名字列表. Catholicon 是一部于公元 1286 年完成的拉丁词典, 它是第一部描述将单词按字母顺序排序的规则的著作, 而不仅仅是前几个字母.
- 1946 年, John Mauchly 在摩尔学校讲座中首次提到二分搜索, 这是一门开创性和基础的大学计算机课程.
- 1957 年, William Wesley Peterson 发表了第一个插值搜索方法.
- 1960 年, 当 Derrick Henry Lehmer 发布了适用于所有数组的二进制搜索算法时, 每个已发布的二进制搜索算法仅适用于长度小于 2 的 1 次方的数组.
- 1962 年, Hermann Bottenbruch 提出了二分搜索的
ALGOL 60实现, 将最后比较相等, 将平均迭代次数增加一, 但将每次迭代的比较次数减少到一. - 统一二分搜索由斯坦福大学的 AK Chandra 于 1971 年开发.
- 1986 年, Bernard Chazelle 和 Leonidas J. Guibas 引入了分数级联作为解决计算几何中众多搜索问题的方法
标准二分法
给定一个具有 $n$ 的元素的有序数组 $A$, 排序为 $A_0 \leq A_1 \leq \cdots \leq A_{n+1} $ 和 目标值 $T$, 下面是利用二分在 $A$ 中查找 $T$ 的说明.
- 令 $L = 0$ 并且 $R = n-1$
- 如果 $L > R$ 则搜索失败, 程序终止
- 令 $m = floor(\frac{L+R}{2})$, 即 $m$ 是小于或者等于 $\frac{L+R}{2}$ 的最大整数
- 如果 $A_m < T$, 则令 $L = m+1$, 并转到第 2 步
- 如果 $A_m > T$, 则令 $R = m-1$, 并转到第 2 步
- 如果 $A_m = T$, 搜索完成; 返回 $m$
伪代码如下所示:
function binary_search(A, n, T) is
L := 0
R := n − 1
while L ≤ R do
m := floor((L + R) / 2)
if A[m] < T then
L := m + 1
else if A[m] > T then
R := m − 1
else:
return m
return unsuccessful二分法变种
上面的方法使用的是 $floor$ 取的中间值, 还可以通过 $ceil(\frac{L+R}{2})$ 来取. 如果目标值在数组中出现多次, 这可能会改变结果.
上述过程中, 算法会在每次迭代中检查中间元素 $A[m]$ 是否等于目标 ($T$). 有些实现会在每次迭代忽略这个检查, 仅剩一个元素时才执行此检查 (当 $L = R$ 时). 这样的话每次迭代都会消除一次比较.
Hermann Bottenbruch 在 1962 年发布了第一个省略此检查的实现.
- 令 $L = 0$ 并且 $R = n-1$
- 当 $L \neq R$ 时
2.1 令 $m = ceil(\frac{L+R}{2})$, 即 $m$ 是大于或者等于 $\frac{L+R}{2}$ 的最小整数
2.2 如果 $A_m > T$, 则令 $R = m-1$
2.3 其他情况下, $A_m \leq T$, 则令 $L = m$ - 最后 $L = R$, 如果 $A_L = T$, 则返回 $L$. 否则, 搜索不成功, 程序终止
伪代码如下:
function binary_search_alternative(A, n, T) is
L := 0
R := n − 1
while L != R do
m := ceil((L + R) / 2)
if A[m] > T then
R := m − 1
else:
L := m
if A[L] = T then
return L
return unsuccessful二分法的坑
虽然二分查找的基本思想比较简单, 但细节却出奇的棘手. 唐纳德. 克努斯
当 Jon Bentley 将二进制搜索作为专业程序员课程中的一个问题时, 他发现 90% 的人在经过几个小时的工作后都未能提供正确的解决方案, 主要是因为不正确的实现无法运行或在极少数情况下返回错误的答案边缘情况.
1988 年发表的一项研究表明, 它的准确代码仅在二十本教科书中的五本中找到. 此外, Bentley 自己的二分搜索实现 (发表在他 1986 年的《Programming Pearls 》一书中) 包含一个溢出错误, 二十多年来一直未被发现. Java 编程语言二进制搜索的库实现在九年多的时间里都有相同的溢出错误.
在实际实现中, 用于表示索引的变量通常具有固定大小 (整数), 这可能导致非常大的数组的算术溢出. 如果跨度的中点计算为 $\frac{L+R}{2}$, 那么值 $L+R$ 可能超出用于存储中点的数据类型的整数范围, 即使 $L$ 和 $R$ 都在范围内. 如果 ${\displaystyle L}$ 大号和 ${\displaystyle R}$ 是非负的, 这可以通过计算中点来避免 $L + \frac{R-L}{2}$.
如果未正确定义循环的退出条件, 则可能会发生无限循环. 一旦 $L$ 超过 $R$, 搜索失败, 必须传达搜索失败. 此外, 当找到目标元素时必须退出循环, 或者在将检查移到最后的实现的情况下, 必须在最后检查搜索是成功还是失败. Bentley 发现, 大多数错误地实现二分搜索的程序员在定义退出条件时都犯了错误.
重复元素
该过程可能返回其元素等于目标值的任何索引, 即使数组中有重复的元素. 例如, 如果要搜索的数组是 $[1, 2, 3, 4, 4, 5, 6, 7]$ 目标是 $4$, 那么算法返回第 4 个 (索引 3) 或第 5 个 (索引 4) 元素是正确的. 在这种情况下, 常规过程将返回第 4 个元素 (索引 3). 它并不总是返回第一个副本 (考虑 $[1, 2, 3, 4, 4, 5, 6, 7]$ 它仍然返回第四个元素). 但是, 有时需要为在数组中重复的目标值找到最左边的元素或最右边的元素. 在上面的示例中, 第 4 个元素是值 4 的最左侧元素, 而第 5 个元素是值 4 的最右侧元素. 如果存在这样的元素, 上述替代过程将始终返回最右侧元素的索引.
如果数组中有多个元素为 $v$, 上面的函数输出的是哪一个下标呢? 不难想到应该是靠近中间的那一个, 那么怎么求出值等于 $v$ 的完整区间呢?
下面的代码为求下界的函数, 当 $v$ 存在时返回它出现的第一个位置. 如果不存在, 返回这样一个下标 $i$: 在此处插入 $v$ (原来的元素 $A[i]$, $A[i+1]$ 等全部向后移动一个位置) 后序列依然有序.
二分查找求下界:
int lower_bound(int *A, int left, int right, int val) {
int mid;
while (left < right) {
mid = left + (right - left) / 2;
if (A[mid] >= val)
right = mid;
else
left = mid + 1; // 插入后前面不变, 那么应该输出原后一个的下标
}
return left;
}思路如下:
- $A[mid]$ 等于 $val$, 至少已经找到一个, 但前面可能还有, 所以区间为 $[left, mid]$
- $A[mid]$ 大于 $val$, 所求的位置不可能在后面, 但可能为 $mid$, 区间为 $[left, mid]$
- $A[mid]$ 小于 $val$, 所求的位置不可能在前面, 也不会为 $mid$, 区间为 $[left+1, mid]$
合并得到 $A[mid]$ 大于等于 $val$, 区间变为 $[left, mid]$, $A[mid]$ 小于 $val$, 区间变为 $[mid+1, right]$.
类似的可以写出求上界的函数, 但注意: 最后求出的查找区间是左闭右开的区间 $[left, right)$, 所以求上界的函数是这样的: 当 $val$ 存在时返回它出现的最后一个位置的后面一个位置. 如果不存在, 返回这样一个下标 $i$: 在此处插入 $val$(原来的元素 $A[i]$, $A[i+1]$ 等全部向后移动一个位置) 后序列依然有序.
二分查找求上界:
int lower_bound(int *A, int left, int right, int val) {
int mid;
while (left < right) {
mid = left + (right - left) / 2;
if (A[mid] <= val)
left = mid + 1;
else
right = mid;
}
return left;
}版权声明: 本文为 CSDN 博主「SeasonJoe」的原创文章, 遵循 CC 4.0 BY-SA 版权协议, 转载请附上原文出处链接及本声明.
原文链接:https://blog.csdn.net/SeasonJoe/article/details/49975819
近似匹配
二分法题目
二分查找法代码实现
// 二分查找法
// A[]为严格递增序列, left 为二分下界, x 为欲查询的数
// 二分区间为左闭右闭的[left, right], 传入的初值为[0, n-1]
int binarySearch(int A[], int left, int right, int x){
int mid;
while (left <= right){
mid = (left + right) / 2; // mid = left + (right - left) / 2;
if (A[mid] == x){
return mid;
} else if (A[mid] > x){
right = mid - 1;
} else if (A[mid] < x){
left = mid + 1;
}
}
return -1;
}二分法求序列中第一个大于等于 x 的元素的位置 L
// 求序列中第一个大于等于 x 的元素的位置 L
// 二分上下界为左闭右闭的[left, right], 传入的初值为[0, n]
int lower_bound(int A[], int left, int right, int x) {
int mid;
while (left < right){
mid = (left + right) / 2;
if (A[mid] >= x) {
right = mid;
} else {
left = mid + 1;
}
}
return left; // 返回夹出来的位置
}二分法求序列中第一个大于 x 的元素的位置 R
int upper_bound(int A[], int left, int right, int x) {
int mid;
while (left < right){
mid = (left + right) / 2;
if (A[mid] > x) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}二分法解决"寻找有序序列第一个满足某条件的元素的位置"问题的固定模板
// 二分区间为左闭右闭[left, right], 初值必须能覆盖解的所有取值
int solve(int left, int right) {
int mid;
while (left < right) {
mid = (left + right) / 2;
if (条件成立) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}二分法求根号 2 的近似值
double calSqrt(){
double left = 1, right = 2, mid; // [left, right] = [1, 2]
while (right - left > eps) {
mid = (left + right) / 2;
if (f(mid) > 2) {
right = mid;
} else {
left = mid;
}
}
return mid;
}二分法求某个单调函数根的近似值
// 利用二分法求单调函数的根
const double eps2 = 1e-5;
double f(double x){
return ...; // 写函数的表达式
}
double solve(double L, double R){
double left = L, right = R, mid;
while (right - left > eps2){
mid = (left + right) / 2;
if (f(mid) > 0){
right = mid;
} else{
left = mid;
}
}
return mid;
}快速幂的递归写法 (二分法实现)
// 快速幂的递归写法
typedef long long LL;
// a^b & m
LL binaryPow(LL a, LL b, LL m){
if (b == 0)
return 1;
if (b & 1){ // 如果 b 为奇数
return a * binaryPow(a, b - 1, m) % m;
} else{
LL mu = binaryPow(a, b / 2, m);
return mu * mu % m;
}
}二分使用实战
1030 完美数列 (25 分)
给定一个正整数数列, 和正整数 p, 设这个数列中的最大值是 $M$, 最小值是 $m$, 如果 $M \le mp$, 则称这个数列是完美数列.
现在给定参数 $p$ 和一些正整数, 请你从中选择尽可能多的数构成一个完美数列.
输出格式: 在一行中输出最多可以选择多少个数可以用它们组成一个完美数列.
分析: 输入数据到数组, 对数组进行排序, 对每个元素用二分法求出第一个大于 $a[i] * p$ 的元素的位置 $j$, $(j - i)$ 即为完美数列的长度, 将所有长度取最大值即为结果.
代码: 这里用到了上面求序列中第一个大于 x 的元素的位置 R 的函数 upper_bound().
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
using namespace std;
long long a[100010] = { 0 };
long long upper_bound(long long A[], long long left, long long right, long long x){
long long mid;
while (left < right){
mid = (left + right) / 2;
if (A[mid] > x){
right = mid;
} else{
left = mid + 1;
}
}
return left;
}
int main()
{
freopen("in.txt", "r", stdin);
long long ans = 1; // 存储" 完美数列" 的最大长度
long long n, p;
scanf("%lld %lld", &n, &p);
// 读取输入
for (long i = 0; i < n; i++){
scanf("%lld", &a[i]);
}
// 排序
sort(a, a + n);
// 遍历数组, 对每个元素都查找最大值的位置 j, 区间长度与 ans 比较, 取较大者
for (long long i = 0; i < n; i++){
// 寻找第一个大于 a[i] * p 的元素的位置
long long j = upper_bound(a, i + 1, n, a[i] * p);
ans = max(ans, j - i);
}
printf("%lld\n", ans);
fclose(stdin);
return 0;
}二分查找 Demo
// int j = lower_bound(pairsOfIntervals.begin(), pairsOfIntervals.end(), end) - pairsOfIntervals.begin();
int l = 0, r = n, mid;
// seek lower bound
while(l < r) {
int mid = (r + l) >> 1;
if ((*pairsOfIntervals[mid].second)[0] >= end) {
r = mid;
} else {
l = mid + 1;
}
}总结
翻译整理自: 维基百科.
文章评论