代码模板
板子题
记诵口诀:男左女右 (判断为true时区间所在的位置) 男是一 +1 女是零 不加
r和l离check判定ture的范围最近的等于mid
同时二分的终点是满足check条件的最接近分界线的值
bool check(int x) {/* ... */} // 检查x是否满足某种性质
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid; // check()判断mid是否满足性质
else l = mid + 1;
}
return l;
}
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
AC代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=1e5+10;
int q[N];
int n,m;
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
cin>>q[i];
}
while(m--)
{
int k;
cin>>k;
int l=0,r=n-1;
while (l<r)
{
int mid= l+r >>1;//mid被划分在右边则不需要加1
if(q[mid]>=k)
r=mid;
else
l=mid+1;
}
if(q[l]!=k)
cout<<"-1 -1"<<endl;
else
{
cout<<l<<" ";
l=0,r=n-1;
while(l<r)
{
int mid= l+r+1 >>1;
if(q[mid]<=k)
l=mid;
else
r=mid-1;
}
cout<<l<<endl;
}
}
}