Problem7665--学习系列 —— 二分 —— 二分查找上界

7665: 学习系列 —— 二分 —— 二分查找上界

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

SubmitSolved: 0Submit Num: 0StatisticsShowOff!

Description

【问题引入】

很多时候，简单的二分查找并不能满足我们的要求。
例如，我们要在下面的数据中查找最后一个 $5$ 的位置。
存储下标   1 2 3 4 5 6 7 8 9
数值       3 5 5 5 5 5 5 5 8
如上所示，最后一个数字 $5$ 出现在第 $8$ 个位置。我们称这类问题为二分查找上界，可以用在二分查找，也可以用在二分答案。整个思路和标准二分查找一样。

【步骤 $1$】

我们需要从 $[1,9]$ 中找数据 $5$，因此 $l=1,\ r=9$。由于 $l<r$，我们可以使用二分来查找。这样 $m=(l+r+1)/2=(1+9+1)/2=5$。注意，这里和二分查找下界的不同。
此时，$a[5]=5$，二分查找并没有完成，我们需要进一步缩小区域，看是否还有数据 $5$ 的存在。
根据二分的特性，$[1,4]$ 这个区间，肯定不会存在答案。答案只能在 $[5,9]$ 这个区间，注意 $a[5]$ 是可能的。
因此，我们使用 $m$ 的数据更新 $l$，即 $l=m$。也就是说，我们继续 $[l,r]$，即 $[5,9]$ 这个区间进行二分查找。

【步骤 $2$】

我们需要从 $[5,9]$ 中找数据 $5$，因此 $l=5,\ r=9$。由于 $l<r$，我们可以使用二分来查找。这样 $m=(l+r+1)/2=(5+9+1)/2=7$。
此时，$a[7]=5$，二分查找并没有完成，我们需要进一步缩小区域，看是否还有数据 $5$ 的存在。
根据二分的特性，$[5,6]$ 这个区间，肯定不会存在答案。答案只能在 $[7,9]$ 这个区间，注意 $a[7]$ 是可能的。
因此，我们使用 $m$ 的数据更新 $l$，即 $l=m$。也就是说，我们继续 $[l,r]$，即 $[7,9]$ 这个区间进行二分查找。

【步骤 $3$】

我们需要从 $[7,9]$ 中找数据 $5$，因此 $l=7,\ r=9$。由于 $l<r$，我们可以使用二分来查找。这样 $m=(l+r+1)/2=(7+9+1)/2=8$。
此时，$a[8]=5$，二分查找并没有完成，我们需要进一步缩小区域，看是否还有数据 $5$ 的存在。
根据二分的特性，$[7,7]$ 这个区间，肯定不会存在答案。答案只能在 $[8,9]$ 这个区间，注意 $a[8]$ 是可能的。
因此，我们使用 $m$ 的数据更新 $l$，即 $l=m$。也就是说，我们继续 $[l,r]$，即 $[8,9]$ 这个区间进行二分查找。

【步骤 $4$】

我们需要从 $[8,9]$ 中找数据 $5$，因此 $l=8,\ r=9$。由于 $l<r$，我们可以使用二分来查找。这样 $m=(l+r+1)/2=(8+9+1)/2=9$。
此时，$a[9]=8>5$，根据二分的特性，$[9,9]$ 这个区间，肯定不会存在答案。因此答案一定在 $[8,8]$ 这个区间。
因此，我们使用 $m-1$ 的数据更新 $r$，即 $r=m-1$。也就是说，我们继续 $[l,r]$，即 $[8,8]$ 这个区间进行二分查找。

【步骤 $5$】

我们需要从 $[8,8]$ 中找数据 $5$，因此 $l=8,\ r=8$。由于 $l<r$ 不成立，二分查找结束。
对应的答案为 $2$。也就是最后一个数字 $5$ 出现在第 $8$ 个位置。

Input

【伪代码】 

如果 l<r 成立继续:
    更新 m=(l+r+1)/2
	以 a[m] 为界限判断条件是否成立
	如果 a[m]<=x，说明答案在区间 [m,r] 
	如果 a[m]>x，说明答案在区间 [l,m-1]
返回答案 l

Output

【C++代码】 

const int N=2e6+10;
LL a[N];

//在 [l,r] 中找最后一个 x 的下标 
//<=x max  即小于等于 x 的最大值 
bool check2(LL m,LL x) {
	//以 a[m] 为界限判断二分是否成立
	return a[m]<=x;
	 
}
LL bsearch2(LL l, LL r, LL x) {
	while (l<r) {
		LL m=(l+r+1)/2;
		if (check1(m, x)) {
			l = m;
		} else {
			r = m-1;
		}
	}
	return l;
}

Source/Category

 
Submit