AKSZ-二分算法

Kenny

2024-03-31 17:33:16

发布于：广东

14阅读

0回复

0点赞

二分查找

手写输入

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f-=1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
int main(){
	int n;
	n=read();
	cout << n;
	return 0;
}

加速cin

#include<bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(0); //cin党必备，关闭同步流 
	cin.tie(0);
	
	int n;
	cin >> n;
	cout << n; 
}

随机数生成

#include<bits/stdc++.h>
using namespace std;
int main(){
	freopen("data.in","w",stdout); //写在data.in 
	
	//随机数种子
	mt19937 rnd(time(NULL)); //int数据
	int x=1+rnd()%10; //生成1~10的数据
	cout << x << endl; 
	return 0;
}

想到思路后怎么做？

只能敲暴力
先敲正解，调试过样例，文件过大样例
写暴力对拍，生成随机测试数据，有错改错
检查是否写上freopen（）

二分查找是什么

二分查找（也被称为折半查找）是一种在有序数组中查找特定元素的搜索算法。它的基本思想是：

首先确定待搜索数组的中间元素。
将目标元素与中间元素进行比较。
如果目标元素等于中间元素，则查找成功，返回中间元素的索引。
如果目标元素小于中间元素，则在数组的左半部分继续搜索。
如果目标元素大于中间元素，则在数组的右半部分继续搜索。
不断重复上述过程，直到找到目标元素或搜索范围为空。

二分查找的关键在于每次都将搜索范围减半，这使得其时间复杂度达到O(log n)，其中n是数组中元素的数量。这种算法非常高效，特别是对于大型有序数组的搜索。然而，它要求输入数组必须是完全有序的。如果数组无序，通常需要先进行排序，这会增加额外的时间复杂度。对于小规模数据或频繁插入/删除元素的数据结构，二分查找可能不如其他算法高效。

二分模板

#include<bits/stdc++.h>
using namespace std;
int n;
int x;
int a[105]; 
bool check(int mid){
	return /*判断条件*/;
}
int main(){
	ios::sync_with_stdio(0); //cin党必备，关闭同步流 
	cin.tie(0);
	cin >> n;
	for(int i=1;i<=n;i++) cin >> a[i];
	cin >> x;
	int ans=-1; 
	int l=1,r=n; //二分的上下边界 
	//在[l,r]闭区间 开区间[l,r)不包括最后一个节点
	while(l<=r){ //例题 不够模板 
		int mid=(l+r)>>1;
		if(check(mid)){ //check条件 
		    ans=mid;
			r=mid-1;
		}else{
			l=mid+1;
		}
	} 
	cout << ans;
	return 0;
}

有帮助，赞一个

去预览

0/2000

这里空空如也