3. 二分查找-变形1 不会！！！！！！

[陈榆鑫 (“良人王”楚天秋)]

3. 二分查找-变形1
   题目ID：9331必做题100分
   最新提交：
   Time Limit Exceeded
   0 分
   历史最高：
   Time Limit Exceeded
   0 分
   时间限制: 1000ms
   空间限制: 262144kB
   题目描述
   二分查找：输入
   n
   n 个从小到大的有序数，使用二分查找第一个大于
   m
   m 的数的位置（计数从 1 开始）。

输入格式
第一行一个整数
n
n，第二行
n
n 个整数
a
i
a
i
​
表示要查找的有序数列，第三行若干个整数
m
i
m
i
​
表示要查找的数字（最多有
S
S 个）。

输出格式
输出若干个空格分隔的整数，代表第一个比
m
i
m
i
​
大的数的位置。如果没有这样的数输出
n
+
1
n+1 。

样例
Input 1
7
1 2 2 4 5 7 9
2 3 4 10
Output 1
4 4 5 8
数据范围
0
<
n
≤
1
0
5
0<n≤10
5
，
0
≤
a
i
≤
1
0
6
0≤a
i
​
≤10
6
，
0
≤
m
i
≤
1
0
6
0≤m
i
​
≤10
6
，
0
<
S
≤
1000
0<S≤1000

[毛思源 (洛谷)]

It is hard.

[陈榆鑫 (“良人王”楚天秋)]

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int a[N];
int n,x;
int main(){
cin>>n;
for(int i = 1;i<=n;i++) cin>>a[i];
while(cin>>x){
int l = 1,r = n;
int ans = -1;
while(l<=r){
int mid = (l+r) / 2;
if(a[mid] > x){
ans = mid;
r = mid - 1;
}
else if(a[mid] < x){
l = mid +1;
}
}
if(a[ans] > x) cout<<ans+1<<" “;
else cout<<n+1<<” ";
}

return 0;

}
代码TLE了

[钱雨辰 (上弦二 童磨)]

下次发题目麻烦格式化一下qwq

[毛思源 (洛谷)]

只能用1层循环

[陈榆鑫 (“良人王”楚天秋)]

删哪个？

[毛思源 (洛谷)]

或者用scanf和printf.

[陈榆鑫 (“良人王”楚天秋)]

还是不会

[徐昊宇]

const int N=1e5+10;
int a[N];
int n,x;
int main(){
ios::sync_with_stdio(0);cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
while(cin>>x){
int l=1,r=n,ans=n+1;
while(l<=r){
int mid=l+r>>1;
if(a[mid]>x) ans=mid,r=mid-1;
else l=mid+1;
}
cout<<ans<<" ";
}
return 0;
}

[毛思源 (洛谷)]

TLE了？

[陈榆鑫 (“良人王”楚天秋)]

改好了，else if换成else，删掉两个大扩号就ok了

[毛思源 (洛谷)]

关帖