二分思想

前言：二分法是一种应用广泛的基础算法，可以在二分查找与二分答案的问题中得到应用。因其O（logn）的时间复杂度，在处理较大数据有着较高的效率。

基本原理：二分法通过将一个有序数组从中间分成两半，比较中间值与目标值的大小，从而将范围缩小，在左半部分或右半部分继续查找，直至找到目标值或者确定目标值不存在。

时间复杂度：O（logn）。其中n是数组长度。因为每次操作将范围缩小一半，是将n除以2^x得到最后的一个结果，所以最多logn次即可找到结果。

二分查找

c++代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int binarySearch(const vector<int>& arr, int target) {
    int l = 0, r = arr.size() - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return -1;
}

这个模板实现了基础的二分查找功能。

库函数
lower_bound 和 upper_bound 是 C++ 标准库 中提供的两个非常实用的二分查找函数，主要用于在有序序列中查找元素，下面为你详细介绍。
功能概述
lower_bound：用于在有序序列中查找第一个不小于给定值的元素的位置。也就是说，它会返回一个迭代器，指向序列中第一个大于等于目标值的元素，如果序列中所有元素都小于目标值，则返回序列的尾后迭代器。
upper_bound：用于在有序序列中查找第一个大于给定值的元素的位置。同样返回一个迭代器，指向序列中第一个大于目标值的元素，如果序列中所有元素都不大于目标值，则返回序列的尾后迭代器。

二分答案

二分查找题目一般明显可以看出需要使用二分法。二分答案则在一些较为复杂问题中通过二分法解决问题。经过题目的练习，我们总结出一些经典的二分使用场景。如查找一个数组中第一个大于等于某个值的元素的位置。究其本质，是在问题的解的空间单调且有界的情况下，进行最优解的查找。如果当前解是有效但不是最优解或者无效解，进行区间的更新，从而找到最优答案。

下面是一道经典二分答案题目：
跳石头
题目寻找最短跳跃距离的最大值，可以鉴定为二分题目。下一步需要寻找问题解空间的单调性与有界性。在这一道题目中具体而言，问题解空间就是跳跃距离，区间左端点是0，右端点是全长。在此区间内进行二分查找，进行判断中点值mid是否满足题目条件（即移走石头数量小于题给数量。对每块石头进行遍历，将mid作为最短跳跃距离，如果有比mid更小的就移走石头，否则就继续遍历。最后进行判断石头数量是否符合要求）。二分时当前最短跳跃距离mid符合条件但不是最大的话就更新左区间以寻找更大的最短跳跃距离；如果mid是无效解就更新右区间寻找有效解。

附ac代码：

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
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;
int l, n, m;
int a[50005];

bool judge(int x) {
    int shitou = 0;
    int now = 0;
    for (int i = 0; i <= n; i++) {
        if (x > a[i + 1] - a[now]) {
            shitou++;
        } else {
            now = i + 1;
        }
    }
    if (shitou > m) return false;
    return true;
}

int main() {
    cin >> l >> n >> m;

    a[0] = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    a[n + 1] = l;
    int left = 0;
    int right = l;

    while (left < right) {
        int mid = left + (right - left + 1) / 2;
        if (judge(mid)) left = mid;
        else right = mid - 1;  
    }
    cout << left << endl;
    return 0;
}

一些其他注意事项：

中间值计算

整数二分：
向下取整：当更新策略是 l = mid + 1 和 r = mid 时，使用 mid = l + (r - l) / 2 进行向下取整，避免越界问题。
向上取整：当更新策略是 l = mid 和 r = mid - 1 时，使用 mid = l + (r - l + 1) / 2 进行向上取整，防止死循环。
浮点数二分：直接使用 mid = (l + r) / 2 计算中间值，因为浮点数没有整数的取整问题。

边界更新

整数二分：
l = mid + 1 和 r = mid：当中间值不满足条件时，更新左边界 l = mid + 1；当中间值满足条件时，更新右边界 r = mid。这种更新方式常用于寻找满足条件的最小值。
l = mid 和 r = mid - 1：当中间值满足条件时，更新右边界 r = mid - 1；当中间值不满足条件时，更新左边界 l = mid。这种更新方式常用于寻找满足条件的最大值。
浮点数二分：
由于浮点数没有整数的离散性，更新时直接将边界更新为中间值，即当中间值满足条件时，r = mid；当中间值不满足条件时，l = mid。

终止条件

整数二分
while (l < r)：循环结束后，l 和 r 相等，此时的值即为所求的答案。
while (l <= r)：循环结束后，需要根据具体问题判断 l 或 r 是否为最终答案。
浮点数二分
精度控制：设定一个极小的精度值 eps，当 r - l < eps 时，认为已经找到了满足精度要求的近似解。
迭代次数控制：通过指定迭代次数来终止二分过程，通常迭代次数越多，结果越精确。

题单与视频讲解

洛谷二分题单
MOOC北大郭烨