二分专题1：寻找指定元素（整数查找）

转载已于 2023-08-15 21:52:08 修改 · 粉丝可见 · 115 阅读 · 0 · 0 · 本内容遵循CC 4.0 BY-SA版权协议原文链接：https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/132297193

题目：

样例1：

`cobol<br/>5 3<br/>1 2 3 5 8<br/>`

`cobol<br/>2<br/>`

样例2：

`cobol<br/>5 6<br/>1 2 3 5 8<br/>`

`diff<br/>-1<br/>`

解题：

二分法中，需要注意的细节就是

搜索区间的是否合法即 while() 循环条件的 l 和 r 的控制

左右都是闭区间写法：

代码详解如下：

#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_Finds()
{
	int l = 0,r = n - 1;	// 这里  r  == n - 1 就是可以搜索最后的一个元素
    
    // 这里 因为 l 和 r 都是合法的搜索，不会数组越界
    // 所以这里  l <= r 
	while(l <= r)
	{
		int mid = l + r >> 1;
        
        // 这里  r = mid - 1 就是当前的 mid 一定不是 == m
        // 没必要进入下一次循环搜索
		if(v[mid] > m) r = mid - 1;
        
        // 这里的  l  同理       
		else if(v[mid] < m) l = mid + 1;

		else return mid; 
	}
	return -1;
}

int main()
{
	___G;
	cin >> n >> m;
	for(int i = 0;i < n;++i) cin >> v[i];

	cout << two_Finds() << endl;

	return 0;
}

最后提交：

左闭右开区间的写法：

代码详解如下：

#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_Finds()
{
	int l = 0,r = n;	// 这里  r  == n - 1 就是可以搜索最后的一个元素

    // 这里 r 一定不能进行搜索，否则会数组越界或者又是重复搜索的原理陷入死循环
	while(l < r)
	{
		int mid = l + r >> 1;
        
        // 这里  r = mid  就是当前的 mid 一定不是 == m,并且 因为是 左闭右开区间
        // 所以可以  r = mid
        // 没必要进入下一次循环搜索
		if(v[mid] > m) r = mid;
        
        // 这里的  l  同理       
		else if(v[mid] < m) l = mid + 1;

		else return mid; 
	}
	return -1;
}

int main()
{
	___G;
	cin >> n >> m;
	for(int i = 0;i < n;++i) cin >> v[i];

	cout << two_Finds() << endl;

	return 0;
}