结合模板题,对二分法进行详细分析
笔记:
这是二分法的具体步骤,重点关注第四步的(+1or不+1)问题。
模板题目:题号:789. 数的范围
代码分析:
#include <cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include <cmath>
#include <sstream>
using namespace std;
int n,q,m;
const int N=100010;
int a[N];
int main()
{
scanf("%d%d",&n,&q);
for(int i=0;i<n;i++) scanf("%d",&a[i]);
for(int i=0;i<q;i++)
{
scanf("%d",&m);
int l=0,r=n-1;///对左右两个边界进行初始定义
while (l<r)
{
int mid=(l+r)/2; //取中间,进行二分
if(a[mid]>=m) r=mid;
else l=mid+1;
}
if(a[r]==m) //二分循环以等于所求值结束,此时l=r
{
cout << r << ' ';
r=n-1;
while(l<r) //接下来是对第二个位置的寻找
{
int mid=(l+r+1)/2; //此处+1了,因为更新方式为l=mid
if(a[mid]<=m) l=mid; //带等于号的一边不需要+1/-1 不带的一边要考虑
else r=mid-1 ;
}
cout << r << endl;
}
else cout << "-1 -1" << endl;
}
return 0;
}