如何写一个二分

• 标准格式

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条件，把剩下的那个作为答案