!!!二分模板

如何写一个二分

  • 标准格式
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条件,把剩下的那个作为答案
全部评论

相关推荐

06-12 16:23
已编辑
小米_软件开发(准入职员工)
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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