二分模板

发表于

二分

本文只考虑闭区间即[l,r]

lower_bound

查找第一个大于等于x的数
查找左边界边界，因为当l>r时跳出，即l为r后一位时跳出，所以r始终要在左边界前面一位，所以当a[mid]>=x时r=mid-1

1
2
3
4
5
6
7
8
9
10
int binary_lower_bound(int l,int r,int x){
	int mid;
	while(l<=r){
		mid=l+r>>1;
		if(a[mid]<x){
			l=mid+1;
		}else r=mid-1;
	}
	return l;
}

upper_bound

查找第一个大于x的数
查找第一个大于c的数，循环在l>r时跳出，即r后一位时跳出，所以r只需比所求值小一位，所以当a[mid]>x时，r向左移动r-mid-1

1
2
3
4
5
6
7
8
9
10
int binary_lower_bound(int l,int r,int x){
	int mid;
	while(l<=r){
		mid=l+r>>1;
		if(a[mid]<=x){
			l=mid+1;
		}else r=mid-1;
	}
	return l;
}

其他模板

左边界

跳出循环条件为l==r,r为左边界时跳出。所以a[mid]==左边界,当a[mid]==x时,r=mid;

1
2
3
4
5
6
7
8
9
int left_bound(int l,int r,int x){
	while(l<r){
		int mid=l+r>>1;
		if(a[mid]<x){
			l=mid+1;
		}else r=mid;
	}
	return l;
}

右边界

跳出循环条件为l==r,r为左边界时跳出。所以a[mid]==左边界,当a[mid]>x时,r需要向左靠近所以r=mid-1;

1
2
3
4
5
6
7
8
9
int right_bound(int l,int r,int x){
	while(l<r){
		int mid=l+r+1>>1;
		if(a[mid]<=x){
			l=mid;
		}else r=mid-1;
	}
	return l;
}