zzoce 🧊
二分

二分

Fri Oct 04 2024
zzcoe
2 分钟
数据结构与算法 算法
232 字

在递增序列中查找>=x的最小值#

CPP
1
2
3
4
5
6
7
8
9
10
11
12
int dic(int x,int y,int z){
	int l=x,r=y;
	while (l<r){
		int mid=(l+r)/2;
		if (a[mid]>=z){
			r=mid;
		}else {
			l=mid+1;
		}
	}
	return a[l];
}

在递增序列中查找<=x的最大值#

CPP
1
2
3
4
5
6
7
8
9
10
11
12
int dic(int x,int y,int z){
	int l=x,r=y;
	while (l<r){
		int mid=(l+r+1)/2;
		if (a[mid]<=z){
			l=mid;
		}else {
			r=mid-1;
		}
	}
	return a[l];
}

特点#

两个主要的区分在于取mid的方法不同，并且在mid=(l+r)/2时mid不会背取到r；在mid=(l+r+1)/2时mid不会被取到l。这是对于区间[1,n]可以分别扩充到[1,n+1]以及[0,n]，如果最后的返回值落在了扩充的区间边界上就证明在该区间内无解。

两个二分查找的函数#

lower_bound返回首个不小于Mdp的迭代器 int low= lower_bound(dp+1,dp+n+1,Mdp)-dp; lower_bound返回首个大于Mdp的迭代器 int low= upper_bound(dp+1,dp+n+1,Mdp)-dp;