有基础班_第七课_二分查找
2025-05-29 18:21:57
发布于：上海
21阅读
0回复
0点赞
| 题目 |
|---|
| 解密QQ号 |
| 鱼的记忆 |
| 程序输入问题 |
| 查找 x |
| 第一个大于等于 x 的数 |
| 第一个大于 x 的数 |
| 【二分查找】最后一个小于等于 x |
解密QQ号
题目大意
小码酱给了一串加密的数字字符串（最多 位），它是她的 QQ 号的加密形式。
解密规则如下：
- 将第 个数从串头取出，记入解密后的 QQ 号；
- 将第 个数移动到串尾；
- 删除第 个数，记入 QQ 号；
- 移动第 个数到串尾；
- ...
依此类推，交替执行“删除加入结果”与“移动到尾部”操作，直到队列中只剩一个数字，将它也删掉并加入结果。
题意分析
这个过程非常符合**队列结构（FIFO）**的行为：
- 每次处理当前队首元素；
- 若处于“删除并加入结果”轮次，则记录下来；
- 若处于“移到尾部”轮次，则将该元素重新加入队尾；
- 直到队列为空，整个解密结束。
解题思路
- 将字符串中每个字符依次入队；
- 使用一个标志变量（如
turn = true/false）控制当前操作是“删除加入结果”还是“移动到队尾”； - 持续处理队首元素，直到队列清空。
时间复杂度分析
- 每个字符最多被操作两次（一次加入结果，一次移动到尾）；
- 所以总时间复杂度为 ，其中 为字符串长度，最多为 ；
- 空间复杂度也是 。
代码演示
#include <iostream>
#include <queue>
using namespace std;
int main() {
queue<char> q;
char ch;
// 输入加密串
while (cin >> ch) {
q.push(ch);
}
bool pick = true; // true 表示取出输出，false 表示移到末尾
while (!q.empty()) {
if (pick) {
cout << q.front(); // 输出并删除
q.pop();
} else {
q.push(q.front()); // 移到末尾
q.pop();
}
pick = !pick; // 操作交替
}
cout << '\n';
return 0;
}
鱼的记忆
题目大意
小码君正在学习字符，但他的记忆力有限，他最多能同时记住 个字符。
给定一个长度为 的字符序列，当他遇到不认识的字符时会查看书本：
- 若当前记忆未满，则将该字符加入记忆；
- 若当前已记满 个字符，则先忘掉最早记住的那个，再记住新字符；
- 若字符已在记忆中，则不需要查看书本。
求整个过程中，小码君总共查看书本的次数。
题意分析
本题等价于一个固定长度的先进先出缓存队列（FIFO），当缓存中没有某元素时，需要“缓存替换”。
我们要模拟这个缓存系统，判断每个字符是否已经存在于缓存中，若没有则计数并按规则更新队列。
解题思路
- 使用一个队列
q模拟小码君的记忆，最大长度为 ； - 遍历输入的 个字符：
- 如果字符已存在于
q中，跳过； - 否则：
- 查看书本，计数器加一；
- 如果队列未满，直接加入；
- 如果已满，弹出队首（最早记住的字符），再加入新字符；
- 如果字符已存在于
- 最终输出查看书本的总次数。
优化技巧
- 为避免每次都线性扫描队列判断字符是否存在，可以使用
unordered_set<char>或set<char>进行快速查找； - 当前代码用纯
queue实现，也可通过两次循环保证正确性（当前数据范围 足够使用此法）。
时间复杂度分析
原始实现：
- 每次判断字符是否已在队列中，复杂度 ；
- 总共 个字符，整体复杂度 ；
由于 ，，所以最大操作量为 ，可以接受。
代码演示
#include <iostream>
#include <queue>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
queue<char> q; // 记忆队列
int cnt = 0; // 查看书本次数
for (int i = 1; i <= n; i++) {
char c;
cin >> c;
bool found = false;
int size = q.size(); // 为避免队列长度变化干扰，先记录大小
// 检查是否已记住字符（通过旋转实现判断）
for (int j = 0; j < size; j++) {
char front = q.front();
q.pop();
if (front == c) found = true;
q.push(front);
}
if (!found) {
cnt++; // 需要查看书本
q.push(c); // 加入记忆
if (q.size() > m) q.pop(); // 若超出记忆容量，忘掉最早的
}
}
cout << cnt << endl;
return 0;
}
程序输入问题
题目大意
程序员在敲代码时可能会出现错误，采用如下两种方式进行补救：
- 退格符
#：表示撤销上一个字符； - 退行符
@：表示整行清空，即撤销从上一个换行符到当前位置之间的所有输入。
你将获得若干行输入数据，每一行都表示一次输入，直到遇到 ****** 为止。
请你模拟每一行的输入处理过程，输出最终每一行的“有效字符串”。
题意分析
该问题需要模拟用户的输入行为，本质上是：
- 对字符流进行逐个解析；
- 支持 “撤销最后一个字符” 的栈操作；
- 支持 “清空整行” 的栈清空操作。
因此，非常适合使用 栈（stack） 来实现：
- 入栈表示输入字符；
#表示弹出栈顶；@表示清空整个栈；- 最终将栈内字符拼接还原为字符串即为所求。
解题思路
- 读取每一行字符串，直到遇到结束标志
"******"； - 对于每一行，使用一个栈模拟编辑过程：
- 普通字符：压入栈；
#：如果栈不为空，则弹出一个字符；@：清空整个栈；
- 最后将栈中字符倒序拼接为最终结果字符串；
- 每一行输出一行结果。
时间复杂度分析
- 每行最多处理 个字符；
- 每个字符处理操作为 ；
- 假设总共有 行，总复杂度为 ，其中 是每行长度，最大为 ；
代码演示
#include <iostream>
#include <string>
#include <stack>
using namespace std;
int main() {
string s;
while (getline(cin, s)) {
if (s == "******") break;
stack<char> ss;
for (int i = 0; i < s.length(); i++) {
if (s[i] == '#') {
if (!ss.empty()) ss.pop(); // 退格
}
else if (s[i] == '@') {
while (!ss.empty()) ss.pop(); // 退行
}
else {
ss.push(s[i]); // 正常字符入栈
}
}
// 栈转字符串
string ans = "";
while (!ss.empty()) {
ans = ss.top() + ans;
ss.pop();
}
cout << ans << '\n';
}
return 0;
}
查找 x
题目大意
给定一个升序排列的长度为 的整数序列，所有元素互不相同。
请你查找某个整数 是否存在于该序列中：
- 如果存在，输出 在序列中的位置（下标从 开始）；
- 如果不存在，输出 。
题目要求使用 二分查找 完成。
题意分析
由于序列是升序且无重复元素，非常适合使用二分查找进行快速定位。
解题思路
使用经典的二分查找模板：
- 设置左右指针 （注意从 开始）；
- 每次取中点 ；
- 判断：
- 若 ，则找到了，输出 ；
- 若 ，说明目标在左侧，令 ；
- 若 ，说明目标在右侧，令 ；
- 循环结束后若未找到，则输出 。
时间复杂度分析
- 每次查找将搜索区间缩小一半；
- 最多执行 次比较；
- 所以时间复杂度为 ；
- 对于 ，效率非常高。
代码演示
#include <iostream>
using namespace std;
int main() {
int a[110];
int n, x;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
cin >> x;
int l = 1, r = n;
while (l <= r) {
int mid = (l + r) / 2;
if (a[mid] == x) {
cout << mid << endl;
return 0;
} else if (a[mid] > x) {
r = mid - 1;
} else {
l = mid + 1;
}
}
cout << -1 << endl;
return 0;
}
第一个大于等于 x 的数
题目大意
给定一个长度为 的升序序列（可能包含重复元素），请你查找第一个大于等于某个数 的元素的下标（从 开始）。
如果这样的元素存在，输出其下标；如果不存在（即 比所有元素都大），也要输出 。
题意分析
这是一个经典的二分查找变形问题，即找第一个满足条件的下标（也叫左侧边界查找）。
给定序列是升序的，允许重复元素，目标是：
找到第一个 的下标 。
解题思路
采用二分查找模板进行变形：
- 初始化左右边界：；
- 每次取中点 ；
- 判断：
- 若 ，记录当前位置为候选解，并继续向左查找（）；
- 否则，说明当前位置过小，向右查找（）；
- 循环结束后，输出记录的下标（若没找到则为 ）。
时间复杂度分析
- 每轮搜索将范围减半，最多进行 次；
- 所以时间复杂度为 ；
- 空间复杂度为 。
代码演示
#include <iostream>
using namespace std;
int main() {
int a[110];
int n, x;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
cin >> x;
int l = 1, r = n;
int ans = -1;
while (l <= r) {
int mid = (l + r) / 2;
if (a[mid] >= x) {
ans = mid; // 记录当前满足条件的位置
r = mid - 1; // 继续向左缩小查找范围
} else {
l = mid + 1;
}
}
cout << ans << endl;
return 0;
}
第一个大于 x 的数
题目大意
给定一个升序数组（可能有重复元素），你需要找到其中第一个严格大于某个整数 的元素下标（下标从 开始）。
- 若存在这样的元素，输出其下标；
- 若不存在（即 不小于所有元素），输出 。
题意分析
本题本质是一个标准的二分查找左侧边界问题（upper bound 查找）。
目标是找到最小的 ，使得 成立。
注意与上一题（查找第一个 ）的区别：此题要求严格大于。
解题思路
采用标准二分查找模板进行修改：
- 初始化左右边界 ；
- 使用变量
ans记录满足条件的位置，初始为 ； - 在循环中不断取中点：
- 若 ，说明当前元素可能是答案，同时可能左边还有更小的符合条件的值，故令 ，并记录
ans = mid； - 否则说明 ，不符合要求，向右搜索，令 ；
- 若 ，说明当前元素可能是答案，同时可能左边还有更小的符合条件的值，故令 ，并记录
- 循环结束后输出
ans即可。
时间复杂度分析
- 每轮查找将区间折半，最多执行 次；
- 所以时间复杂度为 ；
- 空间复杂度为 ，不使用额外数组。
代码演示
#include <iostream>
using namespace std;
int main() {
int a[110];
int n, x;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
cin >> x;
int l = 1, r = n;
int ans = -1;
while (l <= r) {
int mid = (l + r) / 2;
if (a[mid] > x) {
ans = mid; // 记录当前可能的答案
r = mid - 1; // 继续在左边查找更小的
} else {
l = mid + 1; // 向右查找
}
}
cout << ans << endl;
return 0;
}
【二分查找】lower_bound 函数
题目大意
给定一个升序排列（元素可能重复）的长度为 的整数序列，要求使用 lower_bound 函数，查找第一个 大于等于 的元素，并输出其下标（从 开始）。
题意分析
这是标准的二分查找变形题，要求使用 STL 中的 lower_bound 函数。
什么是 lower_bound？
- 在一个有序区间中，
lower_bound(first, last, x)返回第一个不小于 的位置； - 它等价于：在区间中找最小的下标 满足 ；
- 若不存在满足条件的元素，返回
last。
解题思路
- 输入数据时从下标 开始存储；
- 使用
lower_bound(a + 1, a + n + 1, x)来查找； - 最后返回的是一个指针，减去
a即可得到下标； - 若 比所有元素都大，返回的下标会是 ，即越界，也符合题意（即没找到）；
- 如需判断是否找到，可加判断
if (pos <= n)。
- 如需判断是否找到，可加判断
时间复杂度分析
lower_bound内部是用二分查找实现的；- 时间复杂度为 ；
- 空间复杂度为 。
代码演示
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int a[110];
int n, x;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
cin >> x;
// 使用 lower_bound 查找第一个 >= x 的元素位置
int pos = lower_bound(a + 1, a + n + 1, x) - a;
cout << pos << endl;
return 0;
}
【二分查找】upper_bound 函数
题目大意
给定一个长度为 的升序序列（元素可能重复），查找第一个 严格大于 的元素的位置，并输出其下标（从 开始）。
本题要求使用 STL 的 upper_bound 函数来实现。
题意分析
这是一个经典的 二分查找右边界 问题，即：
在升序序列中找第一个满足 的位置。
函数说明
upper_bound(begin, end, x)
- 作用：返回第一个严格大于 的位置；
- 实现方式：标准二分查找；
- 时间复杂度：；
- 返回的是一个指针/迭代器，需要通过减去基地址转换为下标。
解题思路
- 将输入数组从下标 开始读入；
- 使用
upper_bound(a + 1, a + n + 1, x)查找； - 该函数返回的是指针，减去
a得到下标； - 若 大于等于所有元素，则返回 ，表示“未找到”。
代码演示
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int a[110];
int n, x;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
cin >> x;
// 使用 upper_bound 找第一个 > x 的元素
int pos = upper_bound(a + 1, a + n + 1, x) - a;
cout << pos << endl;
return 0;
}
【二分查找】最后一个小于等于 x
题目大意
给定一个升序数组（元素可能重复），要求找到最后一个小于等于给定整数 的元素下标（从 开始）。如果找不到，输出 。
题意分析
这是一个二分查找右边界问题，即：
在升序序列中查找最大的 ，使得 。
解题思路
我们可以使用以下三种方法实现该查找：
方法一：STL upper_bound
int pos = upper_bound(a + 1, a + n + 1, x) - a - 1;
原理解释：
upper_bound(first, last, x)返回第一个满足 的迭代器；- 所以最后一个 的元素一定在它的前一个位置；
- 故：
pos = upper_bound(...) - a - 1。
注意：
- 若
upper_bound返回的是a + 1，说明没有任何元素 ，应特判输出-1。
方法二：用 lower_bound(x + 1) 等价替代
int pos = lower_bound(a + 1, a + n + 1, x + 1) - a - 1;
原理解释：
lower_bound(first, last, x + 1)返回第一个 的位置；- 也就是第一个 的位置；
- 同理，前一个就是最后一个 的位置。
方法三：手写二分查找（推荐掌握）
int l = 1, r = n, ans = -1;
while (l <= r) {
int mid = (l + r) / 2;
if (a[mid] <= x) {
ans = mid; // 满足条件，更新答案
l = mid + 1; // 尝试找更大的位置
} else {
r = mid - 1;
}
}
原理解释：
- 满足 时，继续往右找；
- 记录满足条件的最大下标
ans； - 若找不到，
ans仍为-1。
时间复杂度分析
三种方法均使用二分查找，其时间复杂度为：
完整代码（包含三种方法）
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n, x;
int a[110];
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
cin >> x;
// 方法 1：upper_bound
int pos1 = upper_bound(a + 1, a + n + 1, x) - a - 1;
if (pos1 < 1 || pos1 > n) pos1 = -1; // 特判
// 方法 2：lower_bound(x + 1)
int pos2 = lower_bound(a + 1, a + n + 1, x + 1) - a - 1;
if (pos2 < 1 || pos2 > n) pos2 = -1;
// 方法 3：手写二分查找
int l = 1, r = n, ans = -1;
while (l <= r) {
int mid = (l + r) / 2;
if (a[mid] <= x) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
// 输出三种结果（验证用）
cout << "Method 1 (upper_bound): " << pos1 << endl;
cout << "Method 2 (lower_bound): " << pos2 << endl;
cout << "Method 3 (manual bin): " << ans << endl;
return 0;
}
这里空空如也
有帮助，赞一个