OI学习笔记——[基础算法]二分查找

二分查找有三种主流写法, 此处仅记录好理解, 好背, 对称的一种写法

0 题目描述

\(Kanwuqing\) 有一串升序数列, 他想找到第一个<=n和最后一个>=n的数的下标

1 思路

在写代码之前, 我们先思考一下怎么查找, 考虑下面这个例子(第二行是对应下标, 从 \(1\) 开始存)

\[ 3 \hspace{2em} 5 \hspace{2em} 6 \hspace{2em} 7 \hspace{2em} 9 \hspace{2em} 11 \hspace{2em} 11 \hspace{2em} 11 \hspace{2em} 14 \\ 0 \hspace{2em} 1 \hspace{2em} 2 \hspace{2em} 3 \hspace{2em} 4 \hspace{3em} 5 \hspace{3em} 6 \hspace{2em} 7 \hspace{2em} 8 \]

当 \(n=11\) 时, 我们随便取一个区间, 比如取下标 \(2\)~\(4\), 我们发现, 因为是升序排列, 因此区间的最大值一定是最右端的数, 而 \(9\) 都已经比 \(11\) 小了, 那么这个区间一定是不符合要求的. 同理, 若取 \(8\) 这个单元素区间, 显然也是不符合要求的

由此我们大致有个思路了: 无论一开始的区间有多小, 只要最小值小于 \(n\), 最大值大于 \(n\), 那么这个区间一定是符合要求的, 但不是最终答案. 而二分的过程事实上是一个不断缩小范围的过程, 直到区间缩成了一个点或是直接不存在(右下标小于左下标)

那么如何确定是区间左边不要还是区间右边不要呢? 直觉告诉我们应该用一个值来代表该区间, 而这个值直觉上也知道就是区间的中位数. 只要只要中位数 \(<=n\), 那么区间左半部分就不要了, 因为中位数是左半部分的最大值; 反之, 若中位数 \(>n\), 那么右半部分就不要了.

但是还有一个问题没有解决, 究竟如何缩小范围才能分别确定最后剩下的是最后一个\(<=n\)和第一个\(>=n\)的数呢? 对于同一组数据, 前一种情况得到的结果显然更可能偏右, 因此我们更偏向将左下标往右移才能使整体区间趋势向右; 反之则是将右下标往左移

到这里代码似乎已经呼之欲出了

2 代码实现

首先是读取存储数据

1
2
3
cin >> n >> m;
for(int i=1; i<=n; i++) cin >> a[i];
sort(a+1, a+n+1);  // 注意排序

然后是二分查找的实现, 注意分别的结构, 以及明确更趋向于往哪边移动所决定的代码结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int binary_search1(){
    int l=0, r=n+1;  // 开区间, 初始区间一定要大
    while(l+1 < r){  // 只要大于2个元素
        int mid = floor((l+r) / 2);  // 如果会位运算也可以写 (l+r) >> 2
        if(a[mid] <= m) l = mid;  // 这里是小于等于, 因为要找最后一个小于等于m的数, 更趋向右边
        else r = mid;
    }
    return l;  // 最后l+1>=r
}

int binary_search2(){
    int l=0, r=n+1;  // 开区间, 初始区间一定要大
    while(l+1 < r){  // 只要大于2个元素
        int mid = floor((l+r) / 2);  // 如果会位运算也可以写 (l+r) >> 2
        if(a[mid] >= m) r = mid;  // 这里是小于, 因为要找第一个大于等于m的数, 更趋向左边
        else l = mid;
    }
    return r;  // 最后l+1>=r
}

3 STL实现与用法

在 \(STL\) 中, 也有直接封装好的功能可以直接用. 但是还是建议理解本质算法防止啥时候要自己写

一共有三个函数: - lower_bound: 获取第一个大于等于给定值的下标(即上文中的binary_search1) - upper_bound: 获取第一个大于给定值的下标(即上文中的binary_search2, 不过要在返回值基础上-1) - bsearch: 查找给定值的下标

其中lower_bound和bsearch为包含关系, 即bsearch能做到的lower_bound也能做到, 但如1, 3, 5, 7中用bsearch实现lower_bound的功能就很困难

4 二分答案

这是二分查找的一个用处, 当直接计算答案不方便时, 可以考虑枚举答案, 并加以验证; 而当答案与问题间的关系单调时, 可以用二分查找来使算法更为快速

5 实数范围内的二分

上文中我们是在整数范围内进行二分查找, 这里是在实数范围内进行二分查找, 其实很简单: 只要修改循环停止条件即可

1
2
3
- while(l+1 < r)
+ const double eps = 1e-8;
+ while(abs(l-r) > eps)

6 三分

详细介绍见三分查找

这个方法主要用于寻找单最值函数的最值(该函数导函数不一定连续, 因此不用二分查找导函数零点)

5.1 主要原理

拿单峰函数举例, 任取一段区间 \([l, r]\), 在在该区间内再任取两个点 \(lmid<rmid\), 将这个区间分为三部分, 若 \(f(lmid)<f(rmid)\), 则最值点一定不在 \([l, lmid]\) 上, 以此我们可以将 \(l\) 平移至 \(lmid\), 反之亦然, 直到 \(l\) 和 \(r\) 差值在一个很小的范围内, 取二者中间值即可

千万注意要求的是最小值还是最大值, 以此来根据特定的条件筛选掉特定的范围

由此再加上上文中的实数范围内二分查找, 就可以得到三分查找:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
double f(double x){
    return x*x-4*x+4;
}

// main函数
double l=-1e9,r=1e9;
const double eps=1e-6;
while(r-l > eps){
    double m1=l+(r-l)/3;
    double m2=r-(r-l)/3;
    if(f(m1)<=f(m2)) r=m2;
    else l=m1;
}
cout << fixed << setprecision(6) << (l+r)/2 << " " << f((l+r)/2) << endl;

5.2 算法优化

可以很明显地感觉到 (真的明显吗) 三分查找所需时间极大程度上依赖三分点的选取, 因此若是若干轮前后取到相同的点(如 \(l\) 点和之后某轮的 \(lmid\) 重合), 就可以在下一轮直接计算这个点. 由此, 华罗庚提出使用黄金分割法, 这样分割得到的点的特征是 \(l_1, rmid_2\) 重合, \(r_2, lmid_1\) 重合…

rmid1 和 lmid2 应对齐 ternary

然而这样意味着我们需要另外用两个变量来存前一轮分割点的函数值, 代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
l = -1e9,r = 1e9;
double phi = (sqrt(5)-1)/2;
double lmid = phi * l + (1 - phi) * r;  // 定比分点公式
double rmid = phi * r + (1 - phi) * l;
double f1 = f(lmid);
double f2 = f(rmid);

while(r - l > eps){
    if(f1<=f2){
        r = rmid;
        rmid = lmid;
        f2 = f1;
        lmid = phi * l + (1 - phi) * r;
        f1 = f(lmid);
    }
    else{
        l = lmid;
        lmid = rmid;  // 黄金分割规律
        f1 = f2;
        rmid = phi * r + (1 - phi) * l;
        f2 = f(rmid);
    }
}
cout << fixed << setprecision(6) << (l+r)/2 << " " << f((l+r)/2) << endl;

注意: if-else 判断语句下具体跟哪一段结构很容易搞混