---

二分专题2：寻找指定元素（模板）

原创 于 2023-08-16 15:13:48 发布 · 粉丝可见 · 152 阅读 · 0 · 0 · 本内容遵循CC 4.0 BY-SA版权协议 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/132308504

首先先提一下二分模板：

二分，是 分两种情况，搜索的区间是哪一边。

下面模板代码中的判断性质函数:

bool check(int x){ /*  ...  */ }    // 检查 x 是否满足某种性质   x 为 v[mid]

第一种 情况   区间 [l,r] 分成   [l,mid]   和   [r,mid]  的时候：

模板代码如下：

// 区间[l，r] 被划分成 [l，mid] 和 [mid + 1，r]时使用:
int bsearch_1()
{
	// 这里我更新了别人的模板
	// 因为我们二分的时候需要注意好搜索区间
	// 我们模板用的是 while(l < r)  
	// 所以我们搜索的时候  r == n
	int l = 0,int r = n;
	
	while(l < r)
	{
		int mid = l + r >> 1;
		
		// 这里对应的是 我们的   [l,mid] 
		if(check(v[mid])) r = mid;		
		
		// 这里对应的是 我们的   [mid + 1,r]
		else l = mid + 1;
	}
	
	// 返回我们从左往右搜索的下标
	return l;
}

第二种 情况  区间[l，r]被划分成[l，mid - 1]和[mid，r]时使用:

模板代码如下：

// 区间[l，r] 被划分成 [l，mid - 1] 和 [mid，r]时使用:
int bsearch_2()
{
	// 这里我更新了别人的模板
	// 因为我们二分的时候需要注意好搜索区间
	// 我们模板用的是 while(l < r)  
	// 所以我们搜索的时候  r == n
	int l = 0,int r = n;
	
	while(l < r)
	{
		// 由于我们是二分搜索 右边的区域，
		// 所以我们要记得 r + 1  使得  mid 偏移向右边
		int mid = l + r + 1 >> 1;
		
		// 这里对应的是 我们的   [mid,r] 
		if(check(v[mid])) l = mid;		
		
		// 这里对应的是 我们的   [l,mid - 1]
		else l = mid - 1;
	}
	
	// 返回我们从左往右搜索的下标
	return l;
}

以上我的个人理解。

现在我们开始实践练习一下：

题目1：

样例1：

cobol<br/>5 5<br/>1 4 5 5 7<br/>

2

样例2：

cobol<br/>5 6<br/>1 4 5 5 7<br/>

4

样例3：

cobol<br/>5 8<br/>1 4 5 5 7<br/>

5

解题：

根据题目意思，我们利用函数模板套用即可，代码详解如下：

#include <iostream>
#define endl '\n'
#pragma GCC optimize(3,"Ofast","inline")
#define ___G std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10;
 
int n,m,v[N];
 
inline int two_Find()
{
 
	// 虽然有二分查找 但是还是得注意
	// 控制好搜索区间
	int l = 0,r = n;
 
	// 由于我们是递增的顺序
	// 所以要找到 第一个大于等于 m 
	// 也就是  有效区间在   [l,mid] 
	// 我们要尽可能的插座左边多的元素,所以是  [l,mid]
	while(l < r)
	{
		int mid = l + r>> 1;
		if(v[mid] >= m) r = mid;
		else l = mid + 1;
	}
 
	// 返回左端点的下标，就是我们需要查找符合性质的元素
	return l;
 
}
 
inline void solve()
{
	cin >> n >> m;
 
	for(int i = 0;i < n;++i) cin >> v[i];
 
	cout << two_Find() << endl;
 
}
 
 
int main()
{
	___G;
	int _t = 1;
	// cin >> _t;
	while (_t--)
	{
		solve();
	}
 
	return 0;
}

最后提交：

后面的题型基本上一致，套用模板即可。