!!!二分模板

如何写一个二分

  • 标准格式
int l,r;
//找第一个大于等于x的位置,所求答案为l(等价于r+1)
while(l<=r){
	int mid=(l+r)>>2;
	if(a[mid]>=x)r=mid-1;
	else l=mid+1;
}
//找第一个小于等于x的位置,所求答案为r(等价于l-1)
while(l<=r){
	int mid=(l+r)>>2;
	if(a[mid]<=x)l=mid+1;
	else r=mid-1;
}

解释

第一段

  • 对于每一次进入if:mid指向的都是大于等于x的元素,更新x为小于mid指向元素的第一个元素,无论如何,在l超过r之前(即结束循环前),总会到最后一次遍历使得r指向第一个小于x的数或者x,若指向的是x,则在下一次l会更新至等于r,最终使得l/r-1为x
  • 简单来讲就是,该循环总能使得r指向的是第一个小于x的位置,l指向第一个不小于x的位置

第二段

  • 同理于第一段,循环总使得l指向第一个大于x的位置,r指向第一个不大于等于x的位置

如何区分

  • 其实归根结底就是思考到底是找大于等于还是小于等于,然后把找的东西放进if条件,把剩下的那个作为答案
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-07 13:47
机械打工仔:你自己匿名可以,这么好的公司就别给它匿名了
点赞 评论 收藏
分享
05-19 19:57
蚌埠学院 Python
2237:Gpa70不算高,建议只写排名,个人技能不在多而在精,缩到8条以内。项目留一个含金量高的,减少间距弄到一页,硕士简历也就一页,本科不要写很多
实习,投递多份简历没人回...
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务