题目描述
我们刚刚学习了折半查找,但是还没有自己来实践一下,这一节,你就需要自己实现一个折半查找的程序啦。 给定 N 个整数和 K 个待查找的整数 M1,M2,…,Mk 。如果待查找的整数在给定的 N 个整数中,请输出待查找的整数是数组中第几个元素(从 1 开始计算,第一个元素计 1 而不是0 );
如果待查找的整数不在给定的 N 个整数中,则输出 0 。
输入格式
测评机可能会反复运行程序,每次程序运行后,测评机输入包括三行。
第一行输入两个整数N和 K,分别表示给定的整数总个数和待查找的数的个数;
第二行从小到大输入 N 个整数 Ni,每两个整数之间用一个空格隔开;
第三行输入 K 个整数 Nj ,每两个整数之间用一个空格隔开。
输出格式
输出为一行,包括 K 个部分,每个部分为题目描述中待查找的元素索引或 0 ,K 个部分之间用一个空格分隔。
输出行尾不含多余空格。
样例数据1
input
3 1
1 4 6
4
output
2
样例数据2
input
5 2
1 4 6 7 8
5 1
output
0 1
数据规模与约定
$1\leq n,k,Ni,Nj \leq 10^6$
时间限制:$1 \text{s}$
空间限制:$256 \text{MB}$