二分【1】二分查找框架查找指定元素

二分查找基本思想

几种情况汇总

一。严格递增序列

1.查找本身

2.查找第一个大于等于自己的

3.查找第一个大于自己的

4.严格递减序列

二。有重复元素

1.取其中第一个出现的

2.取其中最后一个出现的

二分查找基本思想

几种情况汇总

一。严格递增序列

1.查找本身

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1000002;
int n,x; 
int num[N];
int mid;
int bis(int num[],int left,int right,int x)
{
	while(left<=right)
	{
		mid=left+(right-left)/2;
		if(num[mid]>x) right=mid-1;
		if(num[mid]<x) left=mid+1;
		if(num[mid]==x)
		{
			for(int i=mid;i>0;i--)
			if(num[i]==x&&num[i-1]!=x) return i;
		}
		
	}
	return -1;
}
int main()
{
	scanf("%d %d",&n,&x);
	for(int i=0;i<n;i++) scanf("%d",&num[i]);
	printf("%d",bis(num,0,n-1,x));
	
	
}

2.查找第一个大于等于自己的

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1000002;
int n,x; 
int num[N];
int mid;
int bis(int num[],int left,int right,int x)
{
	while(left<right)
	{
		mid=left+(right-left)/2;
		if(num[mid]>x||num[mid]==x) right=mid;
		if(num[mid]<x) left=mid+1;
		
	}
	if(num[left]>=x) return left;
	else return left+1;
}
int main()
{
	scanf("%d %d",&n,&x);
	for(int i=0;i<n;i++) scanf("%d",&num[i]);
	printf("%d",bis(num,0,n-1,x));
	
	
}

3.查找第一个大于自己的

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1000002;
int n,x; 
int num[N];
int mid;
int bis(int num[],int left,int right,int x)
{
	while(left<right)
	{
		mid=left+(right-left)/2;
		if(num[mid]>x) right=mid;
		if(num[mid]<x||num[mid]==x) left=mid+1;
		
	}
	if(num[left]>x) return left;
	else return left+1;
}
int main()
{
	scanf("%d %d",&n,&x);
	for(int i=0;i<n;i++) scanf("%d",&num[i]);
	printf("%d",bis(num,0,n-1,x));
	
	
}

4.严格递减序列

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1000002;
int n,x; 
int num[N];
int mid;
int bis(int num[],int left,int right,int x)
{
	while(left<=right)
	{
		mid=left+(right-left)/2;
		if(num[mid]>x) left=mid+1;
		if(num[mid]<x) right=mid-1;
		if(num[mid]==x) return mid;
		
	}
	return -1;
}
int main()
{
	scanf("%d %d",&n,&x);
	for(int i=0;i<n;i++) scanf("%d",&num[i]);
	printf("%d",bis(num,0,n-1,x));
	
	
}

二。有重复元素

1.取其中第一个出现的

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1000002;
int n,x; 
int num[N];
int mid;
int bis(int num[],int left,int right,int x)
{
	while(left<=right)
	{
		mid=left+(right-left)/2;
		if(num[mid]>x) right=mid-1;
		if(num[mid]<x) left=mid+1;
		if(num[mid]==x)
		{
			for(int i=mid;i>0;i--)
			if(num[i]==x&&num[i-1]!=x) return i;return 0;
		}
		
	}
	return -1;
}
int main()
{
	scanf("%d %d",&n,&x);
	for(int i=0;i<n;i++) scanf("%d",&num[i]);
	printf("%d",bis(num,0,n-1,x));
	
	
}

2.取其中最后一个出现的

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1000002;
int n,x; 
int num[N];
int mid;
int bis(int num[],int left,int right,int x)
{
	while(left<=right)
	{
		mid=left+(right-left)/2;
		if(num[mid]>x) right=mid-1;
		if(num[mid]<x) left=mid+1;
		if(num[mid]==x)
		{
			for(int i=mid;i>0;i--)
			if(num[i]==x&&num[i-1]!=x) return i;return 0;
		}
		
	}
	return -1;
}
int main()
{
	scanf("%d %d",&n,&x);
	for(int i=0;i<n;i++) scanf("%d",&num[i]);
	printf("%d",bis(num,0,n-1,x));
	
	
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/692465.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！