#c

C++二分法之二分找答案

从基础到应用的二分查找进阶技巧

#c
@鞠大龙
魅客科创中心

CONTENTS

目录

1. 二分法概述

1.1 二分法概述

  • 二分法是一种基于"分治"思想的算法策略
  • 核心思想：每次将问题规模缩小一半，从而将时间复杂度从降低到
  • 二分法的两种主要应用：
    • 二分查找：在有序数组中查找特定元素
    • 二分找答案：在一个具有单调性的解空间中寻找满足条件的解
返回目录 信息学 C++二分法之二分找答案 魅客科创中心

1.2 二分法概述

二分法的特点：

  • 时间复杂度为，非常高效
  • 适用于具有单调性的问题
  • 可以处理大规模数据
  • 实现简单但细节需要注意
  • 可以解决很多实际问题

二分法的应用领域：

  • 搜索算法
  • 优化问题
  • 数值计算
  • 机器学习（如梯度下降）
  • 游戏开发（如猜数字）
返回目录 信息学 C++二分法之二分找答案 魅客科创中心

2. 二分查找回顾

2.1 二分查找回顾

  • 二分查找是二分法最基础的应用，用于在有序数组中查找特定元素
  • 前提条件：数组必须是有序的（升序或降序）
  • 基本思路:
    • 确定查找范围的左右边界
    • 计算中间位置
    • 将目标值与中间元素比较
    • 根据比较结果，缩小查找范围（左半部分或右半部分）
    • 重复上述步骤，直到找到目标值或确定目标值不存在
返回目录 信息学 C++二分法之二分找答案 魅客科创中心

2.2 二分查找回顾：C++实现

// 在有序数组中查找目标值，返回索引，若不存在则返回-1
int binarySearch(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;  // 防止整数溢出
        
        if (nums[mid] == target) {
            return mid;  // 找到目标值
        } else if (nums[mid] < target) {
            left = mid + 1;  // 目标在右半部分
        } else {
            right = mid - 1;  // 目标在左半部分
        }
    }
    
    return -1;  // 目标值不存在
}
返回目录 信息学 C++二分法之二分找答案 魅客科创中心

2.3 二分查找回顾

二分查找的边界细节

二分查找虽然思路简单，但实现时有几个容易出错的细节：

  1. 循环条件：while (left <= right) 还是 while (left < right)？

    • 使用 <= 时，退出循环后 left > right
    • 使用 < 时，退出循环后 left == right

  2. 中间值计算：mid = (left + right) / 2 可能导致整数溢出，更安全的写法是 mid = left + (right - left) / 2

  3. 边界更新：

    • left = mid + 1 和 right = mid - 1 是常见做法
    • 特殊情况下可能需要 left = mid 或 right = mid
返回目录 信息学 C++二分法之二分找答案 魅客科创中心

3. 二分找答案的概念

3.1 二分找答案的概念

  • 二分找答案是二分法的进阶应用，用于在连续或离散的解空间中寻找满足特定条件的解
  • 核心思想：将解空间一分为二，通过某种判断函数确定答案在哪一半
  • 与二分查找的区别:
    • 二分查找：在有序数组中查找特定值
    • 二分找答案：在解空间中寻找满足条件的临界值
  • 适用条件:
    • 解空间具有单调性（存在一个分界点，一侧满足条件，另一侧不满足）
    • 可以设计一个判断函数check(mid)，用于检验当前解是否满足条件
返回目录 信息学 C++二分法之二分找答案 魅客科创中心

3.2 二分找答案的概念

  • 二分找答案的基本框架：
    • 确定解空间的范围 [left, right]
    • 设计判断函数 check(mid)
    • 在循环中：
      • 计算中间值 mid
      • 调用判断函数 check(mid)
      • 根据结果缩小解空间
    • 返回最终答案
  • 关键点：
    • 正确设计判断函数
    • 正确更新解空间边界
    • 处理精度问题（浮点数情况）
返回目录 信息学 C++二分法之二分找答案 魅客科创中心

3.3 二分找答案的概念

二分找答案的思维模型

想象一个数轴，其中：

  • 左侧区域全部不满足条件
  • 右侧区域全部满足条件
  • 我们要找的是第一个满足条件的位置（临界点）

或者反过来：

  • 左侧区域全部满足条件
  • 右侧区域全部不满足条件
  • 我们要找的是最后一个满足条件的位置（临界点）

二分找答案就是要找到这个临界点，这要求问题具有单调性。

返回目录 信息学 C++二分法之二分找答案 魅客科创中心

4. 二分找答案的应用场景

4.1 二分找答案的应用场景

二分找答案适用于以下场景：

  1. 最大值最小化/最小值最大化问题

    • 求解满足某条件的最小/最大值
    • 例：求解最小化最大值的问题

  2. 计数问题

    • 求解满足特定条件的元素个数
    • 例：有多少个小于等于的元素

  3. 资源分配问题

    • 在有限资源下寻找最优分配方案
    • 例：如何分配资源使得最大收益不低于某个值
返回目录 信息学 C++二分法之二分找答案 魅客科创中心

4.2 二分找答案的应用场景

更多具体应用场景：

  • 运输问题：求解在天内运完所有货物所需的最小运载能力
  • 分割问题：将数组分成个连续子数组，使得各子数组和的最大值最小
  • 安排问题：安排工作使得完成所有工作的最长时间最小
  • 搜索问题：在排序矩阵中查找第k小的元素
  • 优化问题：求解满足某约束条件下的最优解
返回目录 信息学 C++二分法之二分找答案 魅客科创中心

4.3 二分找答案的应用场景

如何识别二分找答案的问题
当你遇到以下特征的问题时，可以考虑使用二分找答案

  • 问题要求找到一个"最大/最小"值，使得某条件成立
  • 问题具有单调性：随着变量增大/减小，条件满足情况呈现单调变化
  • 可以设计一个判断函数，快速检验某个值是否满足条件
  • 解空间范围明确，且可以用二分法高效搜索

关键是识别问题中的单调性，并将其转化为"寻找临界点"的形式。

返回目录 信息学 C++二分法之二分找答案 魅客科创中心

5. 二分找答案的模板代码

5. 二分找答案的模板代码

寻找第一个满足条件的值（最小值）:

// 在[left, right]范围内寻找第一个满足条件的值
int binarySearchFirstTrue(int left, int right) {
    while (left < right) {  
        int mid = left + (right - left) / 2;  
        if (check(mid)) {  
            // mid满足条件，答案可能是mid或更小的值
            right = mid;  
        } else {
            // mid不满足条件，答案一定在mid右侧
            left = mid + 1;  
        }
    }
    // 最终left==right，指向第一个满足条件的位置
    return check(left) ? left : -1;  
}
返回目录 信息学 C++二分法之二分找答案 魅客科创中心

5. 二分找答案的模板代码

寻找最后一个满足条件的值（最大值）：

// 在[left, right]范围内寻找最后一个满足条件的值
int binarySearchLastTrue(int left, int right) {
    while (left < right) {
        // 向上取整，避免死循环
        int mid = left + (right - left + 1) / 2;
        if (check(mid)) {
            // mid满足条件，答案可能是mid或更大的值
            left = mid;
        } else {
            // mid不满足条件，答案一定在mid左侧
            right = mid - 1;
        }
    }
    // 最终left==right，指向最后一个满足条件的位置
    // 需要再次检查这个位置是否真的满足条件
    return check(left) ? left : -1;
}
返回目录 信息学 C++二分法之二分找答案 魅客科创中心

5. 二分找答案的模板代码

浮点数二分查找

当解空间是连续的实数域时，需要使用浮点数二分：

double binarySearchFloat(double left, double right, double epsilon) {
    while (right - left > epsilon) {  // 精度控制
        double mid = left + (right - left) / 2;
        if (check(mid)) {
            right = mid;
        } else {
            left = mid;
        }
    }
    return left;  // 或right，此时两者非常接近
}




注意：

  • 使用精度控制而非固定迭代次数
  • 浮点数比较时要考虑精度问题
  • 通常epsilon设为10^-6或10^-9
返回目录 信息学 C++二分法之二分找答案 魅客科创中心

6. 实例分析

6.1 实例分析：木材加工

问题描述:
有根木材，长度分别为。现在需要将这些木材切割成至少段相同长度的小木材，每段长度必须是整数。求解这些小木材的最大可能长度。如果无法切割出至少段，则返回。

分析:

  • 解空间：小木材的长度，范围是[1, max(L)]
  • 单调性：切割长度越小，得到的小木材段数越多
  • 判断函数：给定长度，检查是否能切割出至少K段
返回目录 信息学 C++二分法之二分找答案 魅客科创中心

6.1 实例分析：木材加工（代码示例）

// 判断函数：给定长度length，是否能切割出至少K段
bool canCut(vector<int>& L, int K, int length) {
    int count = 0;  // 切割出的小木材段数
    
    for (int wood : L) {  
        count += wood / length;  // 每根木材可以切出的段数
    }
    
    return count >= K;  
}

// 主函数：寻找最大可能长度
int woodCutting(vector<int>& L, int K) {
    // 特殊情况处理
    if (L.empty()) return 0;    
    // 确定解空间范围
    int left = 1;
    int right = *max_element(L.begin(), L.end());    
    // 如果无法切割出至少K段，直接返回0
    long long sum = 0;
    for (int wood : L) sum += wood;
    if (sum < K) return 0;    
    // 二分查找
    while (left < right) {  
        // 向上取整，避免死循环
        int mid = left + (right - left + 1) / 2;  
        if (canCut(L, K, mid)) {
            left = mid;  
        } else {
            right = mid - 1;  
        }
    }    
    return left;  
}

复杂度分析:

  • 时间复杂度: O(n log(max(L)))
  • 空间复杂度: O(1)
返回目录 信息学 C++二分法之二分找答案 魅客科创中心

6.2 实例分析：愤怒的牛

问题描述:
有个牛栏，位置为（按升序排序）。现在需要将头牛放入这些牛栏中，每个牛栏最多放一头牛。为了防止牛打架，希望任意两头相邻的牛之间的最小距离尽可能大。求这个最大的最小距离。

分析:

  • 解空间：相邻牛之间的最小距离，范围是[1, (x[N-1] - x[0]) / (C-1)]
  • 单调性：最小距离越大，能放置的牛越少
  • 判断函数：给定最小距离distance，检查是否能放置头牛
返回目录 信息学 C++二分法之二分找答案 魅客科创中心

6.2 实例分析：愤怒的牛（代码示例）

// 判断函数：给定最小距离distance，是否能放置C头牛
bool canPlace(vector<int>& positions, int C, int distance) {
    int count = 1;  // 已放置的牛数量
    int lastPos = positions[0];  // 上一头牛的位置
    
    for (int i = 1; i < positions.size(); i++) {  
        if (positions[i] - lastPos >= distance) {  
            count++;
            lastPos = positions[i];
            
            if (count >= C) {  
                return true;  // 已经放置了C头牛
            }
        }
    }
    
    return false;  
}

// 主函数：寻找最大的最小距离
int angryCows(vector<int>& positions, int C) {
    // 特殊情况处理
    if (positions.size() < C) return -1;   
    // 确保位置已排序
    sort(positions.begin(), positions.end());    
    // 确定解空间范围
    int left = 1;
    int right = positions.back() - positions.front();   
    // 二分查找
    while (left < right) {  
        int mid = left + (right - left + 1) / 2;  
        if (canPlace(positions, C, mid)) {
            left = mid;  
        } else {
            right = mid - 1;  
        }
    }    
    return left;  
}

复杂度分析:

  • 时间复杂度: O(n log(max_distance))
  • 空间复杂度: O(1)
返回目录 信息学 C++二分法之二分找答案 魅客科创中心

6.3 实例分析：跳石头

问题描述:
一条河上有个石头，位置为（按升序排序）。一个人想从河的起点跳到终点，每次只能从一个石头跳到另一个石头。现在需要移除个石头，使得剩余石头之间的最小距离尽可能大。求这个最大的最小距离。

分析:

  • 解空间：相邻石头之间的最小距离，范围是[1, positions[N-1] - positions[0]]
  • 单调性：最小距离越大，需要移除的石头越多
  • 判断函数：给定最小距离distance，检查是否能通过移除不超过M个石头实现
返回目录 信息学 C++二分法之二分找答案 魅客科创中心

6.3 实例分析：跳石头（代码示例）

// 判断函数：给定最小距离distance，是否能通过移除不超过M个石头实现
bool canAchieve(vector<int>& positions, int M, int distance) {
    int removed = 0;  // 已移除的石头数量
    int lastPos = positions[0];  // 上一个保留的石头位置
  
    for (int i = 1; i < positions.size() - 1; i++) {  
        if (positions[i] - lastPos < distance) {  
            removed++;  
        } else {
            lastPos = positions[i];  
        }
        
        if (removed > M) {  
            return false;
        }
    }
    
    return true;  
}

// 主函数：寻找最大的最小距离
int stoneJump(vector<int>& positions, int M) {
    // 特殊情况处理
    if (positions.size() <= 2) return positions.back() - positions.front();   
    // 确保位置已排序
    sort(positions.begin(), positions.end());   
    // 确定解空间范围
    int left = 1;
    int right = positions.back() - positions.front();   
    // 二分查找
    while (left < right) {  
        int mid = left + (right - left + 1) / 2;  
        if (canAchieve(positions, M, mid)) {
            left = mid;  
        } else {
            right = mid - 1;  
        }
    }
    
    return left;  
}
返回目录 信息学 C++二分法之二分找答案 魅客科创中心

6.3 实例分析：跳石头

优化版本:

bool canAchieveOptimized(vector<int>& positions, int M, int distance) {
    int count = 0;  // 需要移除的石头数量
    int curr = 0;   // 当前石头的索引
    int next = 1;   // 下一个石头的索引    
    while (next < positions.size()) {  
        if (positions[next] - positions[curr] < distance) {  
            count++;  
            next++;
        } else {
            curr = next;  
            next++;
        }        
        if (count > M) {  
            return false;
        }
    }    
    return true;  
}

复杂度分析:

  • 时间复杂度: O(n log(max_distance))
  • 空间复杂度: O(1)
返回目录 信息学 C++二分法之二分找答案 魅客科创中心

7. 练习题推荐

7.1 初级练习题

  1. [POJ 2456] Aggressive cows

    • 难度：★★☆☆☆
    • 描述：在一条直线上有N个牛栏，需要将C头牛放入这些牛栏中，使得相邻两头牛之间的最小距离最大化
    • 思路：二分查找可能的距离，检查是否能放置C头牛

  2. [HDU 1969] Pie

    • 难度：★★☆☆☆
    • 描述：有N个不同大小的派，需要分给F+1个人，每人得到的派必须来自同一个派且大小相同，求每人能得到的最大派面积
    • 思路：二分可能的派面积，检查是否能满足F+1人

  3. [LOJ 1201] 运输问题

    • 难度：★★☆☆☆
    • 描述：有N件货物需要在D天内运完，每辆车的容量相同，求所需的最小容量
    • 思路：二分可能的容量，检查是否能在D天内运完
返回目录 信息学 C++二分法之二分找答案 魅客科创中心

7.2 中级练习题

  1. [USACO 2018 Jan Silver] MooTube

    • 难度：★★★☆☆
    • 描述：在视频推荐系统中，给定视频间的相关性，查询与某视频相关性不小于k的视频数量
    • 思路：二分+图遍历，预处理后二分查找

  2. [NOIP 2015] 跳石头

    • 难度：★★★☆☆
    • 描述：在河中的N个石头中移除M个，使得剩余石头间的最小距离最大化
    • 思路：二分可能的最小距离，检查需要移除的石头数

  3. [CSES 1085] Array Division

    • 难度：★★★☆☆
    • 描述：将数组分成k个连续子数组，使得各子数组和的最大值最小
    • 思路：二分可能的子数组和最大值，检查是否能分成k部分
返回目录 信息学 C++二分法之二分找答案 魅客科创中心

7.3 高级练习题

  1. [CSP-S 2021] 交通规划

    • 难度：★★★★☆
    • 描述：在道路网络中设置检查点，使得所有路径都经过至少一个检查点，且最大等待时间最小
    • 思路：二分+图论，检查网络流是否满足条件

  2. [POJ 3258] River Hopscotch

    • 难度：★★★★☆
    • 描述：类似跳石头问题，但起点和终点固定，移除石头使最小距离最大化
    • 思路：二分+贪心，注意边界条件处理

  3. [HDU 1551] Cable master

    • 难度：★★★★☆
    • 描述：有N条电缆，需要切割出K条等长电缆，求最大可能长度
    • 思路：浮点数二分，注意精度控制
返回目录 信息学 C++二分法之二分找答案 魅客科创中心

7.4 综合应用题

  1. [NOIP 2012] 借教室

    • 难度：★★★★★
    • 描述：处理n天的教室借用申请，每天有可用教室数，判断最早哪天的申请无法满足
    • 思路：二分天数+差分数组预处理

  2. [USACO 2017 Open Platinum] COWBASIC

    • 难度：★★★★★
    • 描述：在特殊编程语言中优化循环执行次数，使程序在时限内完成
    • 思路：二分可能的循环次数，模拟执行检查

  3. [IOI 2014] Game

    • 难度：★★★★★
    • 描述：在交互式游戏中通过二分策略猜数字
    • 思路：经典二分查找的变种，考虑交互特性
返回目录 信息学 C++二分法之二分找答案 魅客科创中心

8. 总结

8. 总结

二分找答案的核心要点：

  • 识别问题特征
    • 解空间具有单调性
    • 可以设计判断函数
    • 问题可以转化为寻找临界点
  • 设计解决方案
    • 确定解空间范围
    • 设计正确的判断函数
    • 选择合适的二分模板
    • 注意边界条件和更新方式
  • 常见错误：
    • 解空间范围确定不正确
    • 判断函数设计有误
    • 二分边界更新不当
    • 整数溢出问题
    • 浮点数精度问题
返回目录 信息学 C++二分法之二分找答案 魅客科创中心

8. 总结

二分找答案的优势：

  • 时间复杂度低：O(log n)
  • 适用范围广：可解决多种优化问题
  • 实现相对简单：框架清晰
  • 效率高：比线性搜索快得多

进阶方向：

  • 三分查找：处理凸函数/凹函数
  • 多维二分：处理多变量问题
  • 二分+其他算法：如二分+贪心、二分+动态规划

实践建议：

  1. 先确认问题是否具有单调性
  2. 明确定义解空间的范围
  3. 设计并测试判断函数
  4. 选择合适的二分模板
  5. 注意边界条件和特殊情况
  6. 多做练习，熟能生巧

记住：二分找答案是一种思想，关键在于将问题转化为"寻找满足条件的临界点"的形式。

返回目录 信息学 C++二分法之二分找答案 魅客科创中心
C++二分法之二分找答案

#c

这个讲义使用了Awesome Marp主题的蓝色风格。 演讲者备注不会在演示模式中显示给观众，仅供演讲者参考。 每个关键页面都添加了备注，帮助演讲者更好地讲解内容。

封面页： - 欢迎学生，简要介绍本次课程的主题和目标 - 强调二分找答案是二分查找的进阶应用，是算法竞赛和面试中的常见题型 - 可以简单提及本课程将从基础概念到实际应用，全面讲解二分找答案的思想和技巧