L8.4 - 二分查找、排列组合与质数筛法深度解析（拓展）

🎯 教学目标

  1. 掌握二分查找核心原理：理解边界控制与时间复杂度
  2. 精通排列组合生成算法：实现高效无重复的排列组合
  3. 理解质数筛法机制：掌握埃氏筛与欧拉筛的优化方法
  4. 开发高效算法思维：应对复杂问题的解决方案

📚 核心算法原理

一、二分查找（Binary Search）

1. 算法框架

1
2
3
4
5
6
7
8
9
10
11
12
13
template<typename T>
int binarySearch(const vector<T>& arr, T target) {
    int left = 0, right = arr.size() - 1;  // 闭区间
    
    while(left <= right) {  // 终止条件
        int mid = left + (right - left)/2;  // 防止溢出
        
        if(arr[mid] == target) return mid;
        if(arr[mid] < target) left = mid + 1;  // 调整左边界
        else right = mid - 1;  // 调整右边界
    }
    return -1;  // 未找到
}

2. 关键要点

  • 前提条件：有序数组（单调性）
  • 时间复杂度：O(log n)
  • 边界陷阱：
    • 终止条件 left <= right
    • 中间值计算防溢出
    • 边界更新 ±1 的重要性

二、排列组合算法

1. 全排列（Permutations）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void permute(vector<int>& nums, int start, vector<vector<int>>& res) {
    if(start == nums.size()) {
        res.push_back(nums);
        return;
    }
    
    for(int i=start; i<nums.size(); ++i) {
        swap(nums[start], nums[i]);      // 交换
        permute(nums, start+1, res);     // 递归
        swap(nums[start], nums[i]);      // 回溯
    }
}

// 调用示例
vector<int> nums{1,2,3};
vector<vector<int>> result;
permute(nums, 0, result);

2. 组合（Combinations）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void combine(vector<int>& path, int start, int n, int k, vector<vector<int>>& res) {
    if(path.size() == k) {
        res.push_back(path);
        return;
    }
    
    for(int i=start; i<=n; ++i) {
        path.push_back(i);              // 选择当前元素
        combine(path, i+1, n, k, res);  // 递归下一层
        path.pop_back();                // 取消选择
    }
}

// 生成C(5,3)
vector<vector<int>> combinations;
vector<int> path;
combine(path, 1, 5, 3, combinations);

三、质数筛法

1. 埃拉托斯特尼筛法（Sieve of Eratosthenes）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<bool> sieve(int n) {
    vector<bool> isPrime(n+1, true);
    isPrime[0] = isPrime[1] = false;
    
    for(int i=2; i*i<=n; ++i) {
        if(isPrime[i]) {
            for(int j=i*i; j<=n; j+=i)  // 标记倍数
                isPrime[j] = false;
        }
    }
    return isPrime;
}

// 获取100以内质数
auto primes = sieve(100);

2. 欧拉筛（线性筛法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> eulerSieve(int n) {
    vector<bool> isPrime(n+1, true);
    vector<int> primes;
    
    for(int i=2; i<=n; ++i) {
        if(isPrime[i]) primes.push_back(i);
        
        for(int p : primes) {
            if(i*p > n) break;
            isPrime[i*p] = false;
            if(i%p == 0) break;  // 关键优化
        }
    }
    return primes;
}

💡 原理详解&性能优化技巧

一、排列组合：数学中的“排队”和“分组”

1. 排列（排队游戏）

概念：从一堆东西里 按顺序 选出几个排成一队，不同的顺序算不同的结果。

例子：
你有3本不同的书《A》《B》《C》，想选2本摆到书架上，能摆出多少种不同的顺序？

答案：6种

  • 所有可能：AB、AC、BA、BC、CA、CB
  • 计算方法：
    第一个位置有3种选择，第二个位置剩下2种选择 → 3×2=6

公式：
排列总数 = n × (n-1) × (n-2) × … × (n-k+1)
（n是总数量，k是选的数量）

2. 组合（分组游戏）

概念：从一堆东西里 不管顺序 选出几个组成一组，顺序不同但内容相同算同一种结果。

例子：
从《A》《B》《C》3本书中选2本带出门，有多少种不同的带法？

答案：3种

  • 所有可能：AB、AC、BC
    （BA和AB算同一种，因为带出门的书不需要排序）

公式：
组合总数 = 排列总数 ÷ 顺序不同的重复数
比如：3本选2本 → 3×2 ÷ (2×1) = 3

二、质数筛法：快速找出所有质数的“筛子”

1. 埃拉托斯特尼筛法（简单版筛子）

原理：像用筛子筛沙子，留下质数，筛掉合数。

操作步骤（以找出30以内的质数为例）：

  1. 列出2~30所有数
    [2,3,4,5,6,7,8,9,10,...,30]
  2. 从最小的质数2开始，划掉所有2的倍数（保留2）
    → 划掉4,6,8,10,…30
  3. 找下一个没被划掉的数3，划掉所有3的倍数
    → 划掉9,15,21,27
  4. 继续找下一个数5，划掉5的倍数
    → 划掉25
  5. 重复直到结束，剩下的就是质数

结果：2,3,5,7,11,13,17,19,23,29

缺点：比如6会被2和3重复筛掉，效率不够高。

2. 欧拉筛法（聪明版筛子）

原理：每个合数只被它的最小质因数筛掉，避免重复筛。

操作步骤（同样找出30以内质数）：

  1. 准备一个空盒子放质数，所有数先标记为质数
  2. 从2开始，把2放进质数盒子，然后划掉2×2=4
  3. 到3，放进盒子，划掉3×2=6、3×3=9
  4. 到4，发现4被划掉，划掉4×2=8
  5. 到5，放进盒子，划掉5×2=10、5×3=15、5×5=25
  6. 以此类推…

优点：每个合数只被划一次，速度更快。

核心代码逻辑：

1
2
3
4
5
6
7
8
for (每个数i从2到n) {
    if (i是质数) 加入质数列表;
    for (质数列表中的每个质数p) {
        if (i*p > n) 跳出循环;
        标记i*p为合数;
        if (i能被p整除) 跳出循环; // 关键，避免重复筛
    }
}

三、二分查找的“偷懒”方式（C++ STL版）

1. lower_bound 和 upper_bound 函数

前提：数组必须是从小到大排序好的！

作用：

  • lower_bound(起始地址, 结束地址, 目标值)：
    找到第一个 ​≥目标值​ 的位置
  • upper_bound(起始地址, 结束地址, 目标值)：
    找到第一个 ​**>目标值**​ 的位置

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <algorithm>
using namespace std;

int main() {
    vector<int> nums = {2,4,6,8,10};
    int target = 6;
    
    // 查找第一个≥6的位置（返回指向6的迭代器）
    auto it1 = lower_bound(nums.begin(), nums.end(), target);
    int index1 = it1 - nums.begin(); // 索引2
    
    // 查找第一个>6的位置（返回指向8的迭代器）
    auto it2 = upper_bound(nums.begin(), nums.end(), target);
    int index2 = it2 - nums.begin(); // 索引3
}

2. 判断是否存在目标值

1
2
bool exists = binary_search(nums.begin(), nums.end(), target);
// 返回true或false

3. 实际应用：快速查找区间

1
2
3
4
5
// 在排序好的分数中查80分的人数
vector<int> scores = {65,70,80,80,85,90,90,90};
auto left = lower_bound(scores.begin(), scores.end(), 80);
auto right = upper_bound(scores.begin(), scores.end(), 80);
int count = right - left; // 2个80分

总结表格

内容 核心要点
排列 顺序不同算不同结果，公式是连乘
组合 顺序不同算相同结果，公式是排列数÷顺序重复数
埃氏筛法 简单筛倍数，但会重复筛
欧拉筛法 每个合数只筛一次，效率更高
STL二分查找 用lower_bound和upper_bound快速定位，数组必须先排序

四. 排列去重优化

1
2
3
// 在交换前增加重复判断
if(i != start && nums[i] == nums[start]) 
    continue;

五. 筛法空间优化

1
2
// 使用位操作压缩存储空间
bitset<1000000> isPrime;  // 每个bit表示一个数

🛠️ 实战应用场景

1. 游戏装备组合系统

1
2
3
4
5
// 从n件装备中选出k件的最佳组合
void findBestCombination(const vector<Equipment>& all, int k) {
    vector<bool> selected(all.size(), false);
    // ...回溯算法寻找最优解...
}

2. 质数在加密中的应用

1
2
3
// 生成大质数对
auto primes = eulerSieve(1000000);
int p = primes.back(), q = primes[primes.size()-2];

💣 常见错误分析

1. 二分查找死循环

1
2
3
4
5
6
7
// 错误写法
while(left < right) {
    int mid = (left+right)/2;  // 可能溢出
    if(arr[mid] < target) left = mid;
    else right = mid-1;
}
// 正确写法应调整边界

2. 组合重复问题

1
2
3
// 未处理重复元素导致结果重复
输入：[2,2,3]
输出包含多个[2,2,3]

3. 筛法下标越界

1
2
// 错误写法
for(int j=i; j<=n; j+=i)  // 当i=0时崩溃

📊 算法对比

算法 时间复杂度 空间复杂度 适用场景
标准二分查找 O(log n) O(1) 有序数据查询
全排列 O(n!) O(n) 所有可能排列
埃氏筛法 O(n log log n) O(n) 批量找质数
欧拉筛法 O(n) O(n) 需要质数列表

总结归纳

  1. 二分查找核心
    • 维护搜索区间不变性
    • 注意整数溢出问题
    • 灵活处理变体问题
  2. 排列组合要点
    • 回溯算法的剪枝优化
    • 处理重复元素的去重技巧
    • 组合数的数学公式应用
  3. 质数筛法精髓
    • 埃氏筛法的批量标记思想
    • 欧拉筛法的线性时间复杂度
    • 位操作压缩空间技巧