- 查找给定的K
二分模板
- 2023-7-16 14:59:51 @
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 1E5 + 5;
int n, k, a[N];
void brust() // 朴素做法
{
int f = 0;
for(int i = 1; i <= n; i++)
if(a[i] == k)
{
cout << i << " ";
f = 1;
break;
}
if(f == 1)
cout << k << endl;
else cout << -1 << endl;
}
void handle() // 二分模板
{
int ans = 0;
int left = 1, right = n;
while(left <= right)
{
int mid = (right - left) / 2 + left; // (right + left) / 2
if(a[mid] >= k)
{
ans = mid;
right = mid - 1;
}
else
{
left = mid + 1;
}
}
if(ans && a[ans] == k) cout << ans << " " << k << endl;
else cout << -1 << endl;
}
void initInput()
{
cin >> n >> k;
for(int i = 1; i <= n; i++)
cin >> a[i];
}
int main(void)
{
initInput();
//brust();
handle();
return 0;
}
3 条评论
-
Terro114514 LV 4 @ 2023-7-16 15:17:53
if(a[mid] >= k)
这是啥意思
-
2023-7-16 15:12:02@
666 -
2023-7-16 15:04:59@
谢谢喵
- 1
信息
- ID
- 591
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- 递交数
- 335
- 已通过
- 81
- 上传者