二分简述：
二分算法，又称为二分搜索或折半搜索，是一种在有序数组中查找特定元素的搜索算法。其基本思想是将数组分成两半，然后根据目标值与中间元素的大小关系来决定是继续在左侧还是右侧进行搜索。这个过程会不断重复，直到找到目标值或搜索范围为空为止。
下面是二分算法的一般步骤：
1. 初始化：设置两个指针，一个指向数组的起始位置（low），另一个指向数组的结束位置（high）。此时，low = 0，high = 数组长度 - 1或者low = 1，high = 数组长度 。
2. 循环条件：只要low小于等于high，就继续循环。
3. 计算中间位置：在每次循环中，计算中间位置mid=(low + high) / 2。
4. 比较：比较中间元素与目标值。
- 如果中间元素等于目标值，搜索成功，返回mid。
- 如果中间元素大于目标值，说明目标值在数组的左侧，更新high为mid - 1。
- 如果中间元素小于目标值，说明目标值在数组的右侧，更新low为mid + 1。
5. 循环结束：如果low大于high，说明没有找到目标值，搜索失败。
二分算法的时间复杂度是O(log n)，其中n是数组的长度。这使得它在大规模数据搜索中非常高效。然而，二分搜索的一个前提条件是数组必须是有序的。
二分算法不仅可以用于搜索，还可以用于解决一些优化问题，如找到函数的最大值或最小值等。
双指针简述：
双指针是编程中常用的一种技术，特别是在处理数组和字符串问题时。双指针方法通常涉及在数据结构中使用两个指针来遍历和解决问题。双指针技术可以用于多种算法问题，如查找、排序、搜索子数组或子字符串等。
常见的双指针应用场景：
- 滑动窗口：
- 用于解决连续子数组或子字符串的问题，如最长无重复字符的子串。
- 两个指针定义了一个窗口，随着遍历的进行，窗口的大小和位置会改变。
- 快慢指针（Floyd's Tortoise and Hare Algorithm）：
- 用于检测链表是否有环。
- 一个指针移动速度是另一个的两倍，如果链表有环，它们最终会相遇。
- 两数之和：
- 给定一个数组，找出数组中两个数的和等于特定值。
- 通过一个指针固定一个数，另一个指针遍历数组找到另一个数。
- 反转字符串或链表：
- 使用两个指针分别指向字符串或链表的头部和尾部，逐步交换两指针指向的元素。
- 归并排序：
- 两个指针分别指向已排序的两个子数组，逐步比较并合并。
- 寻找旋转排序数组中的最小值：
- 数组是旋转过的有序数组，使用两个指针找到最小值。
题目链接：3745. 牛的学术圈 I - AcWing题库
由于对计算机科学的热爱，以及有朝一日成为 「Bessie 博士」的诱惑，奶牛 Bessie 开始攻读计算机科学博士学位。
经过一段时间的学术研究，她已经发表了 N篇论文，并且她的第 i篇论文得到了来自其他研究文献的 ci次引用。
Bessie 听说学术成就可以用 ℎ 指数来衡量。
ℎ 指数等于使得研究员有至少 ℎ 篇引用次数不少于 ℎ 的论文的最大整数 ℎ。
例如，如果一名研究员有 4 篇论文，引用次数分别为 (1,100,2,3)，则 ℎ 指数为 2，然而若引用次数为 (1,100,3,3) 则 hℎ 指数将会是 3。
为了提升她的 ℎ 指数，Bessie 计划写一篇综述，并引用一些她曾经写过的论文。
由于页数限制，她至多可以在这篇综述中引用 L 篇论文，并且她只能引用每篇她的论文至多一次。
请帮助 Bessie 求出在写完这篇综述后她可以达到的最大 ℎ 指数。
注意 Bessie 的导师可能会告知她纯粹为了提升 ℎ 指数而写综述存在违反学术道德的嫌疑；我们不建议其他学者模仿 Bessie 的行为。
输入格式
输入的第一行包含 N 和 L。
第二行包含 N个空格分隔的整数 c1,…,cN。
输出格式
输出写完综述后 Bessie 可以达到的最大 ℎ 指数。
数据范围
1≤N≤10^5
0≤ci≤10^5
0≤L≤10^5
输入样例1：
4 0 1 100 2 3
输出样例1：
2
样例1解释
Bessie 不能引用任何她曾经写过的论文。上文中提到，(1,100,2,3) 的 ℎ 指数为 22。
输入样例2：
4 1 1 100 2 3
输出样例2：
3
样例2解释：
如果 Bessie 引用她的第三篇论文，引用数会变为(1,100,3,3)。上文中提到，这一引用数的 ℎ 指数为 3。
题目分析：
此题要求h指数，他可以引用自己的论文增加自己的h指数，最多引用一次，引用一篇则对应的一篇引用加1，所以分界线就在c[i]>=h与c[i]=h-1这里，其他的情况不用管。当c[i]>=h时，无论如何引用都已经大于h了，若想增加就在c[i]=h-1这里，引用一次对应加1，刚好到h，对于c[i]<h-1的无论如何加1都到不了h。我们可以二分查找h指数，当h符合条件，区间给到右区间，寻找有没有更大的选择。
代码实现
二分：
#include<iostream> using namespace std; int n,l; int c[100005]; bool cheak(int mid){//判断此时mid是否符合h指数的条件 int a=0; int b=0; for(int i=1;i<=n;i++){ if(c[i]>=mid){//统计大于等于h的个数 a++; } if(c[i]==mid-1){//统计刚好引用一次到h的个数 b++; } } return a+min(b,l)>=mid;//a+min(b,l)为最终的h } int main(){ cin>>n>>l; for(int i=1;i<=n;i++){ cin>>c[i]; } int l=0,r=n; while(l<r){ int mid=l+r+1>>1; if(cheak(mid)){ l=mid; }else{ r=mid-1; } } cout<<r<<endl; return 0; }
双指针：
#include <bits/stdc++.h> #define int long long using namespace std; const int N = 2e5 + 10; int main() { int n, k; cin >> n >> k; int a[N]; // 存取每个数的个数 int ma = 0; for(int i = 1; i <= n; i ++ ) { int x; cin >> x; a[x] ++ ; ma = max(ma, x); // 记录最大值 } int res = 0; // 最终结果 int sum = n; // 初始化，目前大于0的个数肯定是所有数量 int j = 0; for(int i = 0; i <= ma + 5; i ++ ) { while(sum >= j && i >= j) { // 双指针的重点，个数要比j多，i要比j大 res = max(res, j); // 成立，h指数可以为j j ++ ; } sum -= a[i]; if(sum + min(a[i], k) >= j && i >= j - 1 && k != 0) res = max(res, j); // 处理k } cout << res << endl; return 0; }
二分与双指针算法都可以解决此题，看个人喜欢哪一种算法了，如果二分写的很好，记得很熟悉，可以使用二分，有的人感觉双指针好理解，关键在于个人喜好，解决题目的算法有很多种，但是只要能把题目A掉就是好算法。
笔者水平有限，代码写的一般，若有错误，请大家指正，一起进步。执笔至此，感触彼多，全文将至，落笔为终，感谢大家的支持。
