HBU月考 二分查找（20分）
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：[https://blog.csdn.net/weixin\_42449444/article/details/85621946](https://blog.csdn.net/weixin_42449444/article/details/85621946) 题目描述：
利用二分查找找出所给出的数在数组中的下标。
输入格式:
第一行输入n和m表示数组有n个数据，m表示要对m个数进行查找。
输出格式:
所有输出在一行完成，行末没有多余空格和多余回车。
输入样例:
5 5
1 2 3 4 5
1 2 3 4 5输出样例:
0 1 2 3 4解题思路：
我先用Python写的二分查找算法，提交代码之后直接运行超时。然后我用C++写的二分查找算法，提交之后还是TLE！我嘞个去，Python超时可以理解，C++写的二分查找法还运行超时就有点无语，流下TLE的泪水。然后我放弃二分查找法了，直接无脑用map，map的key值记录数据，value值记录这个数据所在的下标。提交之后还是TLE！于是我加上一条ios::sync_with_stdio(false);语句来取消cin和stdin的同步以减少程序的运行时间，提交代码依旧TLE。无FK说，那我把cout改成printf来减少运行时间好吧，诶哟喂，提交之后完美AC，虽然这题要求的是用二分查找算法求解但是TLE我也没办法啊。
Py二分查找算法：博客链接 （之前写过的代码）
def search(data, item):
start, end = 0, len(data) - 1
while start <= end:
middle = (start + end) // 2
#缩小搜索范围
if item < data[middle]:
end = middle - 1
elif item > data[middle]:
start = middle + 1
else:
return middle
#若没找到,则返回-1
return -1 C++AC代码：
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false); //取消cin和stdin的同步
int n,m;
cin >> n >> m;
map<int,int> mp; //mp的key值记录数据，value值记录该数据的所在下标
for(int i = 0; i < n; i++)
{
int temp;
cin >> temp;
mp[temp] = i;
}
bool isVirgin = true; //判断是不是第一次
for(int i = 0; i < m; i++)
{
int temp;
cin >> temp;
if(isVirgin)
{
printf("%d",mp[temp]);
isVirgin = false;
}
else
{
printf(" %d",mp[temp]);
}
}
return 0;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019-01-02 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录