二分

整数集合上的二分

例题：二分模板题

题目描述

给定一个按照升序排列的长度为 $n$ 的整数数组，以及 $q$ 个查询，对于每个查询，返回一个元素 $k$ 的起始位置和终止位置（位置从 $0$ 开始计数）。如果数组中不存在，则返回$-1,-1$。

输入格式

第一行包含整数 $n$ 和 $q$，分别代表数组长度和询问次数。

第二行包含 $n$ 个整数（整数范围：$[1,10000]$），表示完整数组。

接下来 $q$ 行，每行包含一个整数 $k$，表示一个询问元素。

$1\le n\le 100000,1\le q\le 10000,1\le k\le 10000$

输出格式

共 $q$ 行，每行包含两个整数，表示所求元素的起始位置和终止位置。

如果数组中不存在该元素，则返回 $-1-1$.

输入样例

6 3
1 2 2 3 3 4
3
4
5

输出样例

3 4
5 5
-1 -1

题目分析

首先可以快速想到的朴素做法是，从头到尾扫描一遍序列，便可以以 $O(n)$ 的时间复杂度找到一个目标的起点和终点。但是题目有 $q$ 组询问，总时间复杂度是 $O(n\times q)$，数据范围较大，明显会超时。

题目说给定的序列是有序的，我们能不能利用有序的性质，减少查找的次数从而缩短查找时间呢？

当然可以！由于序列是有序的，我们可以先查找中间值是否等于目标，若不是目标，则比较中间值和目标的大小关系，假设中间值大于目标，由于序列的有序性，中间值后面的值都比目标要大，均可排除，此时我们只需要找中间值前面的值即可。

这样的话，原本需要在 $n$ 个元素中查找，一下子把查找范围缩小了一半！对于缩小范围后的区间，重复刚刚的操作，不断查找中间值，并比较中间值和目标的关系，直到找到目标或查找范围为空停止，这就是二分查找的思想。

时间复杂度：由于每次都将查找范围缩小一半，所需要的查找比较次数为 $log(n)$

下面介绍两个二分查找的算法模板：

模板一：在单调递增序列 $a$ 中查找 $\ge x$ 的最小值（$x$ 或 $x$ 的后继），多个相等的 $x$，返回左边界。（二分查找左侧边界）

bool check1(int mid) {
    if (a[mid] >= x) return true;
    else return false;
}
int bs1(int l, int r) {
    while (l < r) {
        int mid = l+r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

模板二：在单调递增序列 $a$ 中查找 $\le x$ 的最大值（x或x的前驱），多个相等的x，返回右边界。（二分查找右侧边界）

bool check2(int mid) {
    if (a[mid] <= x) return true;
    else return false;
}
int bs2(int l, int r) {
    while (l < r) {
        int mid = (l+r+1) >> 1;  // +1是为了上取整。
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

​上述代码中采用 >> 右移运算符来实现除以 $2$ 的效果，右移运算是向下取整，而整数除法是向零取整，在二分值域包含负数时，后者不能生效。

示例代码

#include <bits/stdc++.h>  
using namespace std;  
  
const int N = 1e5 + 10;  
int a[N], t;  
  
bool check1(int mid)  {  
    return a[mid] >= t;  
}  
  
bool check2(int mid)  {  
    return a[mid] <= t;  
}  
  
  
int bs1(int l, int r) { // 找左边界  
    while (l < r) {  
        int mid = l + r >> 1;  
        if (check1(mid)) r = mid;  
        else l = mid + 1;  
    }  
    return l;  
}  
  
int bs2(int l, int r) { // 找右边界  
    while (l < r) {  
        int mid = l + r + 1 >> 1; // 向上取整，mid 不能更新为r  
        if (check2(mid)) l = mid;  
        else r = mid - 1;  
    }  
    return l;  
}  
  
int main() {  
    int n, q;  
    scanf("%d%d", &n, &q);  
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);  
    while (q--) {  
        scanf("%d", &t);  
        int idx1 = bs1(0, n - 1);  
        int idx2 = bs2(0, n - 1);  
        if (a[idx1] == t)  
            printf("%d %d\n", idx1, idx2);  
        else  
            printf("-1 -1\n");  
    }  
    return 0;  
}

实数域上的二分

例题：数的三次方根

题目描述

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

输入格式

共一行，包含一个浮点数 $n$，$-10000\le n\le 10000$。

输出格式

共一行，包含一个浮点数，表示问题的解，结果保留 $6$ 位小数。

输入样例

1000.0

输出样例

10.000000

题目分析

对于题目给定的数据范围，任何一个数的三次方根 $x$ 都一定满足 $-100\le x\le 100$，我们同样可以考虑二分的思想去求解，先找中间值，再验证中间值是否满足题目条件，对答案范围进行更新。

需要注意的是，因为浮点数在计算机中的计算具备精度上的误差，所以很有可能最后 $l,r$ 无法相等，且 $r$ 会恒大于 $l$ 。
所以一般需要设定一个精度 $eps$，使得左右边界 $l$ 和 $r$ 无限逼近即可，即以 $r-l>eps$ 为循环继续条件，保留 $k$ 位小数时，$eps$ 一般取 ${10}^{-(k+2)}$ 。

另外需要注意的是，因为浮点数本身不会有取整得情况，每次都会严格将区间分成两半，所以在根据 $mid$ 的判定更新 $l$ 或 $r$ 时，皆让其更新为 $mid$ 即可。

示例代码

#include <iostream>
using namespace std;

const double eps = 1e-8;
double n;

bool check(double mid) {
	return mid * mid * mid <= n;
}

int main() {
    cin >> n;
    double l = -100, r = 100;
    while (r - l > eps) {
        double mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }
    printf("%.6lf\n", l);
    return 0;
}

三分法

例题：求单峰函数的极值

题目描述

给定单峰函数的函数式：$f(x)=-(2\ast x-3{)}^2+2$ ，求它的极值点。

输入格式

无

输出格式

共一行，包含一个浮点数，表示问题的解，结果保留6位小数。

输入样例

无

输出样例

无

题目分析

单峰函数的特点是拥有唯一的极值点，在极值点的两侧单调性都严格递增或递减。

以下图所示的单峰函数 $f(x)=-(2\ast x-3{)}^2+2$ 为例，我们可以在函数定义域 $[l,r]$ 上任取两个点 $lmid$ 和 $rmid$，把函数分为三段。

1. 若$f(lmid)<f(rmid)$，则一定为下图的两种情况其一。不管是哪种情况，极大值都在 $lmid$ 的右边，所以可以更新 $l=lmid$。

2. 同理，若 $f(lmid)>f(rmid)$，则极大值点一定在 $rmid$ 的左边，可以更新 $r=rmid$。

每次都取 $lmid$ 和 $rmid$ 为三等分点，则每次更新都可以将搜索范围缩小 $1/3$。三分的前提是函数具有严格单调性，若存在一段值相等的部分，则三分法不再适用。

示例代码

#include<bits/stdc++.h>
using namespace std;
double eps = 1e-8;

double f(double x) {
	return -(2*x-3)*(2*x-3) + 2;
}

bool check(double lmid, double rmid) {
	return f(lmid) < f(rmid);
}

int main() {
	double l = -100, r = 100; // l和r取极值点两侧即可
	while (r - l > eps) {
		double lmid = (2*l + r)/3; // [l,r]区间的 1/3 点
		double rmid = (l+ 2*r)/3;  // [l,r]区间的 2/3 点
		if (check(lmid, rmid)) l = lmid;
		else r = rmid;
	}
	printf("%.6lf", f(l));
	return 0;
}