GESP2026年3月认证C++五级( 第三部分编程题（2）找数）

🌟 题目：找数（两个数组交集）

🧠 一、故事：两支探险队 🧭

有两支探险队：

• 🟦 A队：有 n 个宝藏

• 🟥 B队：有 m 个宝藏

👉 每个宝藏都有一个编号（整数）

👑 国王说：

“统计一下，有多少宝藏同时出现在 A队 和 B队！”

🌟 二、问题本质（非常重要！）

👉 就是：

求两个数组的“交集个数”

🌟 三、最简单理解（暴力方法）

❌方法1：双重循环

for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(a[i] == b[j]) ans++;

❗问题：

👉 时间复杂度：

O(n × m)

👉 太慢！（考试会超时）

🌟 四、聪明方法（二分查找🔥）

🧠故事：图书馆找书 📚

A队的书已经整理好了（排序）

👉 想找一本书：

👉 用“二分查找”！

🌟 五、核心思路（必须掌握！）

🎯步骤：

1️⃣ 先排序 A

sort(a.begin(), a.end());

2️⃣ 遍历 B

对每个 b：

👉 去 A 里面找！

3️⃣ 用二分查找

🌟 六、二分查找详解（重点🔥）

1、🧠故事：猜数字游戏 🎯

你要找一个数：

l = 0, r = n-1

2✨每次：

mid = (l + r) / 2

3、判断：

if(a[mid] > b) r = mid - 1; else if(a[mid] < b) l = mid + 1; else 找到了！

🌟 七、完整代码

#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n, m; cin >> n >> m; vector<int> a(n); // 输入 A for(int i = 0; i < n; i++) cin >> a[i]; // 排序 A（非常关键！） sort(a.begin(), a.end()); int ans = 0; // 遍历 B for(int i = 0, b; i < m; i++) { cin >> b; int l = 0, r = n - 1; bool ok = false; // 二分查找 while(l <= r) { int mid = (l + r) / 2; if(a[mid] > b) r = mid - 1; else if(a[mid] < b) l = mid + 1; else { ok = true; break; } } if(ok) ans++; } cout << ans << endl; return 0; }

🌟 八、举个例子

1、🌰输入：

A = [4, 2, 3] B = [3, 1, 5, 4, 6]

2、✨步骤：

排序 A：

A = [2, 3, 4]

3、遍历 B：

• 找 3 ✔️

• 找 1 ❌

• 找 5 ❌

• 找 4 ✔️

• 找 6 ❌

4、👉 总共：

2 个

🌟 九、复杂度分析

⏱ 时间复杂度：

• 排序：O(n log n)

• 查找：m × O(log n)

👉 总：

O(n log n + m log n)

🌟 十、进阶技巧（高手必备🔥）

🎯方法2：双指针（更快）

1、👉 如果两个数组都排序：

i 指向 A j 指向 B

2、同时移动：

A[i] == B[j] → ans++ A[i] < B[j] → i++ A[i] > B[j] → j++

3、👉 时间复杂度：

O(n + m)

🌟 十一、总结

🎯这类题本质：

👉查找 + 优化

🎯多种解法比较：

🌟 十二、考点回顾：

我们必须掌握：

1️⃣ 二分查找模板（超级重点🔥）

while(l <= r){ mid = (l + r)/2; if(a[mid] > x) r = mid - 1; else if(a[mid] < x) l = mid + 1; else return true; }

2️⃣ 排序 + 查找组合思维

👉 GESP五级考试很多题都是：

排序 + 二分