二分算法

1. 简介与概述、功能介绍

二分查找

二分查找是一种在有序数组中查找特定元素的高效算法。它通过不断将搜索区间缩小一半，逐步逼近目标元素，从而将查找的时间复杂度从线性的 $O(n)$ 降低到对数级别的 $O(log n)$ 。

二分答案

二分答案是二分查找思想的一种拓展应用。当问题的答案具有单调性，且可以通过验证某个答案是否满足条件来判断目标答案在当前猜测值的哪一侧时，就可以使用二分答案算法。通过不断猜测答案，利用验证函数缩小答案所在的区间，最终找到满足条件的最优答案。

2. 适用场景

二分查找

有序数组中查找特定元素：例如在已排序的整数数组中查找某个值的位置。
查找满足特定条件的第一个或最后一个元素：如查找第一个大于等于目标值的元素。

二分答案

求最值问题：当问题是求满足某个条件的最大值或最小值，且答案具有单调性时，可使用二分答案。
决策问题：对于一些判断是否存在满足条件的解的问题，也可以通过二分答案转化为验证问题。

3. 算法原理详解

二分查找

基本思想：在有序数组中，取中间元素与目标元素比较。若中间元素等于目标元素，则查找成功；若中间元素大于目标元素，则在左半区间继续查找；若中间元素小于目标元素，则在右半区间继续查找。不断重复这个过程，直到找到目标元素或搜索区间为空。
区间表示：通常使用左闭右闭区间 $[l, r]$ 表示搜索范围，初始时 $l$ 为数组的第一个元素下标， $r$ 为数组的最后一个元素下标。

二分答案

基本思想：先确定答案的可能范围 $[l, r]$ ，然后取中间值 $mid$ 作为猜测的答案。通过验证函数判断 $mid$ 是否满足条件，如果满足条件，则说明目标答案可能更大，更新左边界 $l = mid$ ；如果不满足条件，则说明目标答案更小，更新右边界 $r = mid - 1$ 。不断重复这个过程，直到 $l = r$ ，此时的 $l$ 就是满足条件的最优答案。
单调性要求：答案必须具有单调性，即如果 $x$ 满足条件，那么所有小于 $x$ （或大于 $x$ ）的值也满足条件，反之亦然。

4. 经典例题及代码实现

二分查找

题面：给定一个升序排列的整数数组 $arr$ 和一个目标值 $target$ ，找出 $target$ 在数组中的下标，如果不存在则返回 -1。 输入样例：

5 3
1 2 3 4 5

输出样例：

示例代码

#include <iostream>
using namespace std;

const int MAXN = 100005;
int arr[MAXN];

// 二分查找函数
int bns(int n, int t) {
    int l = 0, r = n - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (arr[mid] == t) {
            return mid;
        } else if (arr[mid] < t) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return -1;
}

int main() {
    int n, t;
    // 读入数组长度和目标值
    cin >> n >> t;
    // 读入数组元素
    for (int i = 0; i < n; i++) cin >> arr[i];
    // 进行二分查找
    int ans = bns(n, t);
    cout << ans << endl;
    return 0;
}

二分答案

题面：有 $n$ 本书，每本书有一个页数 $p_i$ ，要将这些书分给 $k$ 个人，每个人分到的书必须是连续的，且要求每个人分到的书的总页数尽量均衡，求每个人分到的书的最大总页数的最小值。 输入样例：

4 2
1 2 3 4

输出样例：

示例代码

#include <iostream>
using namespace std;

const int MAXN = 100005;
int p[MAXN];
int n, k;

// 验证函数，判断最大总页数为 x 时是否能满足条件
bool chk(int x) {
    int cnt = 1, sum = 0;
    for (int i = 0; i < n; i++) {
        if (sum + p[i] > x) {
            cnt++;
            sum = p[i];
        } else {
            sum += p[i];
        }
    }
    return cnt <= k;
}

// 二分答案函数
int bna() {
    int l = 0, r = 0;
    for (int i = 0; i < n; i++) {
        l = max(l, p[i]);
        r += p[i];
    }
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (chk(mid)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}

int main() {
    // 读入书的数量和人数
    cin >> n >> k;
    // 读入每本书的页数
    for (int i = 0; i < n; i++) cin >> p[i];
    // 二分答案求解
    int ans = bna();
    cout << ans << endl;
    return 0;
}

5. 总结

二分查找

优点：时间复杂度低，为 $O(log n)$ ，在处理大规模有序数据时效率高。
缺点：要求数组必须有序，对于无序数组需要先进行排序。
适用情况：适用于在有序数组中查找特定元素或满足特定条件的元素。

二分答案

优点：将求最值问题转化为验证问题，通过不断缩小答案区间，降低了问题的复杂度。
缺点：需要问题的答案具有单调性，并且需要设计合适的验证函数。
适用情况：适用于求满足条件的最值问题和一些决策问题。在使用时，要准确判断问题是否满足二分答案的条件，并合理设计验证函数。

例题

Status

Problem

二分算法

On this page