Buer blog | 详情

前面有介绍过二分法是一种高效的搜索算法，用于在有序数组或列表中查找特定元素。该算法通过重复地将数据集分为两半并比较目标值与中间元素来工作，从而快速缩小搜索范围（忘记的同学，可以搜索下上篇文章）。

基本步骤

初始化：确定搜索范围的起始点和结束点。在数组中，这通常是数组的第一个和最后一个元素的索引。计算中间点：找到搜索范围的中间位置。这可以通过将起始点和结束点相加并除以2来实现。比较：将中间位置的元素与目标值进行比较：如果中间元素等于目标值，则找到目标，搜索结束。如果中间元素大于目标值，则目标值只可能在左半部分，因此更新结束点为中间点的前一个位置。如果中间元素小于目标值，则目标值只可能在右半部分，因此更新起始点为中间点的后一个位置。重复：重复步骤2和3，直到找到目标值或确定目标值不在数组中。

时间复杂度

二分法的时间复杂度为O(log n)，其中n是数组中的元素数量。这是因为每次迭代都将搜索空间减半，使得算法非常高效，尤其适用于大型有序数据集。

应用场景

二分法适用于任何已排序的数据集合，用于快速查找特定值。不适用于未排序的数据集合，因为其效率取决于数据的排序状态。

注意事项

二分法要求数据集必须是有序的。在实现时，需要确保正确处理边界条件，以避免无限循环或错误的结果。二分法可以用于各种数据结构，如数组和列表，只要它们支持通过索引快速访问元素。

真题解析

P2678 [NOIP2015 提高组] 跳石头

题目背景

NOIP2015 Day2T1

题目描述

一年一度的“跳石头”比赛又要开始了！

这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 $N$ 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。

为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 $M$ 块岩石（不能移走起点和终点的岩石）。

输入格式

第一行包含三个整数 $L,N,M$，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。保证 $L \geq 1$ 且 $N \geq M \geq 0$。

接下来 $N$ 行，每行一个整数，第 $i$ 行的整数 $D_i,( 0 < D_i < L)$，表示第 $i$ 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。

输出格式

一个整数，即最短跳跃距离的最大值。

样例 #1

样例输入 #1

样例输出 #1

程序源码

#include <bits/stdc++.h>
using namespace std;
#define maxn 500010
int L, N, M; 
int rocks[maxn];// 定义一个数组 rocks，用于存储每个岩石的位置
//内联函数 快速读取 
inline int read() {
    int num = 0, sign = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') sign = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        num = num * 10 + c - '0';
        c = getchar();
    }
    return num * sign;
}
// 定义一个快速读取整数的函数 read，用于从标准输入读取整数，优化输入速度
// 定义一个函数 jemp，用于判断在给定的跳跃距离 x 下，是否可以移走不超过 M 块岩石 
bool jemp(int x) {
    int removed = 0, last = 0;
    for (int i = 1; i <= N + 1; i++) {
        if (rocks[i] - rocks[last] < x) {
            removed++;
        } else {
            last = i;
        }
    }
    return removed <= M;
} 
int main() {
    L = read();
    // 读取起点到终点的距离 L
    N = read();
    // 读取岩石数量 N
    M = read();
    // 读取最多可以移走的岩石数 M
    for (int i = 1; i <= N; i++) {
        rocks[i] = read();
    }
    // 读取每个岩石的位置，并存储在 rocks 数组中
    rocks[N + 1] = L;
    // 将终点的位置添加到 rocks 数组中
    sort(rocks, rocks + N + 2);
    // 对 rocks 数组进行排序，包括起点和终点的位置

    int left = 1, right = L;
    // 初始化二分查找的左右边界
    while (left <= right) {
        int mid = (left + right) / 2;
        // 计算中间值 mid
        if (jemp(mid)) {
            left = mid + 1;
            // 如果 mid 满足条件，则将左边界移动到 mid + 1
        } else {
            right = mid - 1;
            // 如果 mid 不满足条件，则将右边界移动到 mid - 1
        }
    }
    cout << right << endl; // 输出最短跳跃距离的最大值，即二分查找结束时的右边界   
    return 0; 
}