1.区分二分查找与二分答案:
二分查找: 在一个有序的数据集合中进行二分(类似于折半)的方法,找到自己想要的数据,大幅度减小时间复杂度,二分算法的时间复杂度为 O(log n)。
二分答案：答案在某一个区间内，利用二分算法不断地缩小答案区间,最终得到答案。在大多数二分答案的题目中,解题思路一般为：判断+二分
2.二分查找:
(1)在两头闭合的区间中查找目标数据,如 区间[2,3]等。直接上代码--
#include<bits/stdc++.h> using namespace std; const int N = 10005; int n,target,a[N]; int main() { cin>>n>>target; //target为想要查找的数字的值 for(int i=0;i<n;i++) //若i的初始索引为0 { cin>>a[i]; } sort(a,a+n); //使用二分查找算法时，一定是针对单调队列来使用的，所以要先进行排序 int left = 0; int right = n-1; while(left<=right) { int mid = left + (right-left)/2; //数据较小时也许你可以直接写(right+left)/2,在 一些数据较大的题目中,(right-left)/2可以帮助减小数据大小 if(mid>target) { right = mid-1; } else if(mid<target) { left = mid+1; } else { cout<<mid; //mid作为返回值返回的是目标所在的位置 break; } } return 0; }
两头闭合时二分查找算法中最经典的模型,但也有很多要注意的点,比如要先用sort函数排序以保证数据的单调性,以及left和right的取值问题,当for中的i的初始索引为0时,left=0,right=n-1, 当for中i的初始索引是1时,则left=1,right=n。
3.二分答案：
什么是二分答案？
答案属于一个区间，当这个区间很大时，暴力超时。但重要的是——这个区间是对题目中的某个量有单调性的，此时，我们就会二分答案。每一次二分会做一次判断，看是否对应的那个量达到了需要的大小。
判断：根据题意写个check函数，如果满足check，就放弃右半区间（或左半区间），如果不满足，就放弃左半区间（或右半区间），一直往复，直至到最终的答案。
如何判断一个题是不是用二分答案做的呢?
典型特征:
求...最大值的最小 、 求...最小值的最大。
1.求...最大值的最小时，我们二分答案（即二分最大值）的时候，判断条件满足后，尽量让答案往前来（即：让right=mid）
2.求...最小值的最大时，我们二分答案（即二分最小值）的时候，判断条件满足后，尽量让答案往后走（即：让left=mid）
附上一道二分答案的经典题目:
洛谷P2678(跳石头问题)
#include<bits/stdc++.h> using namespace std; const int maxn = 50005; int l,n,m; // m---至多移走的石块 int a[maxn]; int sum[maxn]; bool check(int mid) { int now = 0; int stone = 0; a[0] = 0; for(int i=1;i<=n+1;i++) //有人回想问，为什么要算最后一块石头到终点的距离,最后一块石头不是不可以搬动么，我的回答是:最后终点的那块石头题目不允许搬，但是捏可以搬走他的前一块石头 { if(a[i] - a[now] >= mid) { now = i; } else { stone++; } } if(stone <= m) { return true; } else { return false; } } int main() { cin>>l>>n>>m; for(int i=1;i<=n;i++) { cin>>a[i]; } a[n+1] = l; sort(a,a+n); //二分查找前进行排序是这个数组单调递增 int left = 1; int right = l; int ans = 0; while(right >= left) //二分查找最大距离 { int mid = left + (right - left)/2; if(check(mid)) //检查最大距离是否符合标注 { ans=mid; left = mid + 1; } else { right = mid - 1; } } cout<<ans<<endl; return 0; }
