主页
练习
竞赛
分类
状态
排名
问答
Login
Problem5059--二分模板题
5059: 二分模板题
Time Limit:
2.000 Sec
Memory Limit:
128 MB
Submit:
322
Solved:
109
[
Submit
] [
Status
] [
Web Board
] [Creator:
]
Description
【问题描述】
输入 n(1≤n≤10^6) 个不超过 10^9的单调增的(就是后面的数字大于前面的数字)非负整数 a1,a2,…,an给出一个整数 q(0≤q≤10^9),要求输出这个数字在序列中出现的编号(保证出现)。
【输入格式】
第一行两个整数 n 和 q,表示数字个数和询问的数。
第二行 n 个整数,表示 a。
【输出格式】
q 所在位置。
【输入样例】
11 7
1 3 4 5 7 9 11 13 15 20 21
【输出样例】
5
Sample Input
Sample Output
HINT
#include<bits/stdc++.h>
usingnamespacestd;
intmain() {
intn,q;
cin>>n>>q;
inta[1000001];
for(inti=1; i<=n; i++)
cin>>a[i];
intl=1;
intr=n;
intmid;
while(l<r)
{
mid=(r+l)/2;
if(a[mid]>=q)
r=mid;
else
l=mid+1;
}
cout<<l;
}
Source/Category
[
Submit
] [
Status
]