# 专题二：二分法 ![image.png](https://pic.code-nav.cn/post_picture/1612112775822180354/PyoV3oWo-image.png) # 前言本文主要介绍二分法是什么，二分法的原理，二分法的模板以及使用场景，并且会举一些例题和蓝桥杯真题辅助理解。 # 是什么官方版：二分查找是一个时间效率极高的算法，尤其是面对大量的数据时，其查找效率是极高，时间复杂度是log(n)。主要思想就是不断的对半折叠，每次查找都能除去一半的数据量，直到最后将所有不符合条件的结果都去除，只剩下一个符合条件的结果。精简版：二分区间快速高效找到结果。 # 模板 ## 查找大于等于/大于key的第一个元素这种通常题目描述为满足某种情况的最小的元素。 ```cpp int left = 1,right = n; while(left < right) { //这里不需要加1。我们考虑如下的情况，最后只剩下A[i],A[i + 1]。 //首先mid = i，如果A[mid] > key，那么right = left = i，跳出循环，如果A[mid] < key，left = right = i + 1跳出循环，所有不会死循环。 int mid = (left + right) / 2; if(A[mid] > key)//如果要求大于等于可以加上等于，也可以是check(A[mid]) right = mid; //因为找的是大于key的第一个元素，那么比A[mid]大的元素肯定不是第一个大于key的元素，因为A[mid]已经大于key了，所以把mid+1到后面的排除 else left = mid + 1; //如果A[mid]小于key的话，那么A[mid]以及比A[mid]小的数都需要排除，因为他们都小于key。不可能是第一个大于等于key的元素， } ``` ## 查找小于等于/小于key的最后一个元素这种通常题目描述为满足某种情况的最大的元素. ```cpp int left = 1, right = n; while(left < right) { //这里mid = (left + right + 1) / 2; //考虑如下一种情况，最后只剩下A[i],A[i + 1]，如果不加1，那么mid = i，如果A[mid] < key，执行更新操作后，left = mid，right = mid + 1，就会是死循环。 //加上1后，mid = i + 1,如果A[mid] < key，那么left = right = mid + 1,跳出循环。如果A[mid] > key，left = mid = i，跳出循环。 int mid = (left + right + 1) / 2; if(A[mid] < key) left = mid;//如果A[mid]小于key，说明比A[mid]更小的数肯定不是小于key的最大的元素了，所以要排除mid之前的所有元素 else right = mid - 1;//如果A[mid]大于key，那么说明A[mid]以及比A[mid]还要大的数都不可能小于key，所以排除A[mid]及其之后的元素。 } ``` # 判断二分的特性 1. 单调性：数组具有明显的单调性 2. 二段性：答案在一段区间内，二分答案 # 分类 - 二分查找：在一个已知的有序数据集上进行二分地查找 - 二分答案：答案有一个区间，在这个区间中二分，直到找到最优答案 # 二分思考顺序首先通过题目背景和check(mid)函数的逻辑，判断答案落在左半区间还是右半区间。左右半区间的划分方式一共有两种：中点mid属于左半区间，则左半区间是\[l, mid]，右半区间是\[mid+1, r]，更新方式是r = mid;或者 l = mid + 1;，此时用第一个模板；中点mid属于右半区间，则左半区间是\[l, mid-1]，右半区间是\[mid, r]，更新方式是r = mid - 1;或者 l = mid;，此时用第二个模板（第一个找符合要求的最小值，第二个找符合要求的最大值） # 力扣704：二分查找 ![image.png](https://pic.code-nav.cn/post_picture/1612112775822180354/eLMZuUV0-image.png) ## 代码 ```cpp class Solution { public: int search(vector& nums, int target) { int l=0,r=nums.size()-1; while(l=target) r=mid; else l=mid+1; } if(nums[l]==target) return l; return -1; } }; ``` ## 题解本题就是对模板的理解以及运用，属于是二分查找类型，因此用模板1或者模板2都是可以的，并不涉及最大值与最小值的问题。 # 数的范围 ![image.png](https://pic.code-nav.cn/post_picture/1612112775822180354/VwILZO4c-image.png) ![image.png](https://pic.code-nav.cn/post_picture/1612112775822180354/3LPGwe53-image.png) ## 代码 ```cpp #include using namespace std; const int N=100010; int q[N]; int n,m; int main() { cin>>n>>m; for(int i=0;i>q[i]; while(m--) { int x; cin>>x; int l=0,r=n-1; while(l>1; if(q[mid]>=x) r=mid; else l=mid+1; } if(q[l]!=x) cout<<"-1 -1"<>1; if(q[mid]<=x) l=mid; else r=mid-1; } cout< using namespace std; int n; string str; unordered_set S; //找到任何两个长度为k的子串都不互相同 //知识点：判断某个串是否只出现一次可以用哈希表 bool check(int mid) { for(int i=0;i+mid-1>n; cin>>str; int l=1,r=n;//答案的区间 while(l> 1; if(check(mid)) r=mid; else l=mid+1; } cout< using namespace std; const int N=100010; int w[N], h[N];//存储长、宽 int n,k; //因为答案在一个区间内：具有二段性，因此可以用二分答案法。 bool check(int a){ int num=0;//切出的数量 for(int i=0;i=k) return true; } return false; } int main() { cin>>n>>k; for(int i=0;i>h[i]>>w[i]; int l=1,r=1e5;//答案的区间 while(l>1; if(check(mid)) l=mid;//因为求最大值 else r=mid-1; } cout< #include #include #include using namespace std; const int N = 100010; int n; int h[N]; bool check(int e) { for (int i = 1; i <= n; i ++ ) { e + = e - h[i];//每次失去或者得到能量 if (e >= 1e5) return true;//需要注意超过能量最大值的特判 if (e < 0) return false; } return true; } int main() { scanf("%d", &n); for (int i = 1; i <= n; i ++ ) scanf("%d", &h[i]); int l = 0, r = 1e5;// while (l < r) { int mid = l + r >> 1; if (check(mid)) r = mid; else l = mid + 1; } printf("%d\n", r); return 0; } ``` ## 题解本题还是有一定难度的，首先你需要想到可以用二分答案法来写，因为答案在一个区间内，并且不管你是得到还是失去能量都可以用一个表达式来表示，只不过可以是正也可以负值罢了，再去判断是否有一步走了会小于0，如果小于0了就不符合。本题还需要注意不能超出能量最大值。 # 总结本文主要介绍了二分法，重点需要掌握二分的两个模板和理解方法，灵活运用到题目中还需大家多做题，增加自己的理解力和敏锐度。预祝各位考出好成绩！ ![image.png](https://pic.code-nav.cn/post_picture/1612112775822180354/d6g5W32F-image.png)

专题二：二分法的全部评论