AKSZ-二分查找

CJX

2024-03-31 17:33:28

发布于：广东

8阅读

0回复

0点赞

二分查找

文件读写

freopen(输入文件名, "r", stdin);
freopen(输出文件名, "w", stdout);

程序

fclose(stdin);
fclose(stdout);

输入

$数据量 >= 10^6$

// scanf
scanf("%d",&num);

// cin
ios::sync_with_stdio(0);
cin.tie(0);

// 手写读入
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()
{
	n = read();
	for(int i=0;i<n;i++)
	{
		a[i] = read();
	}
}

数据

随机数

-std=c++11

mt19937 rnd(time(NULL));
rnd();

竞赛

暴力
尝试正解过大样例
对拍，生成随机测试数据，改错
检查文件读写

二分

要求

有序数组
可以比较大小

模板

// 列表nums中第一个大于等于find的数的下标
bool check(int x,int find)
{
	return nums[x] >= find;
}

// O(logn)
sort(&nums[0],&nums[n]); // 确保有序
int l=0,r=n-1,ans = -1;// 上下界 
// 在[l,r]区间查找 
while(l<=r)
{
	int mid;
	mid = (l+r) >> 1;
	if(check(mid,x))
	{
		ans = mid+1;
		r = mid - 1;
		//break;
	}
	else
	{
		l = mid + 1;
	}
	//cout << l << " " << r << endl;
}

升序数组

lower_bound(a,a+n,x)-a;
// 使用于升序数组 lower_bound(数组开头下标,数组结尾下标+1,待查元素) - 数组第0个元素开头
// 返回 第一个 大于等于 待查元素 的 下标，未找到输出n+1

upper_bound(a,a+n,x)-a;
// 使用于升序数组 upper_bound(数组开头下标,数组结尾下标+1,待查元素) - 数组第0个元素开头
// 返回 第一个 大于 待查元素 的 下标