【算法通关指南：算法基础篇】二分算法: 1.A-B 数对 2.烦恼的高考志愿

🔥小龙报：个人主页
🎬作者简介：C++研发，嵌入式，机器人等方向学习者
❄️个人专栏：《C语言》《【初阶】数据结构与算法》
✨ 永远相信美好的事情即将发生

文章目录

• 前言
• 一、A-B 数对
  • 1.1题目
  • 1.2 算法原理
  • 1.3代码
• 二、烦恼的高考志愿
  • 2.1 题目
  • 2.2 算法原理
  • 2.3 代码
• 总结与每日励志

前言

本文将通过两道经典二分查找例题 ——A-B 数对与烦恼的高考志愿，带你系统掌握二分查找的核心思想与实用技巧。从排序预处理到lower_bound、upper_bound的灵活运用，再到手动实现二分与边界细节处理，由浅入深讲解算法原理与代码实现，帮助你快速攻克二分查找题型，提升编程思维与解题效率

一、A-B 数对

1.1题目

链接：A-B 数对

1.2 算法原理

由于顺序不影响最终结果，所以可以先把整个数组排序，来研究是佛否有其他的性质。
由A − B = C 得：B = A − C，由于C是已知的数，我们可以从前往后枚举所有的A ，然后去前面找有多少个符合要求的B ，正好可以用二分快速查找出区间的长度。
【STL使用】
1.lower_bound：传入要查询区间的左右迭代器（注意是左闭右开的区间，如果是数组就是左右指针）以及要查询的值k，然后返回该数组中 >= k的第一个位置。
2.upper_bound ：传入要查询区间的左右迭代器（注意是左闭右开的区间，如果是数组就是左右指针）以及要查询的值k ，然后返回该数组中 > k 的第⼀个位置；

例：a = [10, 20, 20, 20, 30, 40] ，设下标从1 开始计数，在整个数组中查询20 ：lower_bound(a + 1, a + 1 + 6, 20) ，返回a + 2 位置的指针；upper_bound(a + 1, a + 1 + 6, 20) ，返回a + 5 位置的指针；

然后两个指针相减，就是包含20 这个数区间的长度。

1.3代码

#include <iostream>#include <algorithm> using namespace std; typedef long long LL; const int N=2e5+10;LL a[N]; int main(){ int n, c; cin >> n >> c;for(int i =1; i <= n; i++) cin >> a[i];sort(a +1,a +1+ n);LL ret =0;for(int i =2; i <= n; i++){LL b = a[i]- c; ret +=upper_bound(a +1,a + i +1,b)-lower_bound(a +1, a +1+ i, b);} cout << ret << endl;return0;}

注：同时STL的使用范围很「局限」，查询「有序序列」的时候才有用，数组无序的时候就无法使用。但是我们的二分算法也能在「数组无序」的时候使用，只要有「二段性」即可

二、烦恼的高考志愿

2.1 题目

链接：烦恼的高考志愿

2.2 算法原理

先把学校的录取分数「排序」，然后针对每一个学生成绩 ，在「录取分数」中二分出≥ b的「第一个」位置pos，那么差值最小的结果要么在pos位置，要么在位置pos - 1,那么最后的不满意度求法就为：
abs(a[pos] − b)与abs(a[pos − 1] − b)的最小值。

注：细节问题
如果所有元素都大于b的时候，pos − 1 会在0 下标的位置，有可能结果出错；
• 如果所有元素都小于pos的时候，pos会在n的位置，此时结果倒不会出错，但是我们要想到这个细节问题，这道题不出错不代表下⼀道题不出错。
解决方法：加上两个左右护法，结果就不会出错了

2.3 代码

//烦恼的高考志愿 #include <iostream>#include <algorithm> using namespace std; typedef long long LL; const int N=1e5+10;LL a[N],b[N],m,n;LLfind(LL x){ int l =1, r = m;while(l < r){LL mid =(l + r)/2;if(a[mid]>= x) r = mid;else l = mid +1;}return l;} int main(){ cin >> m >> n;for(int i =1; i <= m; i++) cin >> a[i];//设置左护法 a[0]=-1e7;sort(a +1, a +1+ m);LL ret =0;for(int i =1; i <= n; i++){ cin >> b[i];LL pos =find(b[i]); ret +=min(abs(a[pos -1]- b[i]),abs(a[pos]- b[i]));} cout << ret << endl;return0;}

总结与每日励志

✨通过两道题目，我们学会了利用排序与二分查找快速统计数对、寻找最优匹配，理解了边界处理与 STL 函数的正确使用。二分的本质是寻找二段性，代码简洁却考验思维。愿你在算法学习路上保持耐心与专注，每一次思考都在沉淀成长，永远相信美好的事情即将发生，坚持下去，终会遇见更优秀的自己。