1.二分法查找的是边界
2.l和r查找到的是满足不同条件的边界,需根据题意输出具体边界
3.实数二分查找,总觉得闫老师说的不够简单,可能自己是蒟蒻的原因,有些想不通其中原理。
(1)实数二分查找到的也是边界问题。
(2)能够找到问题答案是因为,答案在两个边界之间,两个边界距离足够小,最终确定了一个答案。
最后附上一个我认为好用的实数二分板子。
include[HTML_REMOVED]
using namespace std;
const int N=1000010;
int n,m,q[N];
int main(){
scanf(“%d%d”,&n,&m);
for(int i=0;i[HTML_REMOVED]>1;
if(q[mid]<x) l=mid;
else r=mid;
}
if(q[r]!=x) cout<<"-1 -1"<<endl;
else
{
cout<<r<<' ';
int l=-1,r=n;
while(l+1<r){
int mid=l+r>>1;
if(q[mid]<=x) l=mid;
else r=mid;
}
cout<<l<<endl;
}
}
return 0;
}