A. 二分查找【模板】

内存限制:256 MiB 时间限制:1000 ms 输入文件: bs.in 输出文件: bs.out
题目类型:传统 评测方式:文本比较

题目描述

给定一个 n 个元素有序的(升序)整型数组 a 和 m次查询。

对每次查询,给定一个目标值 t,搜索 数组 a 中是否存在 t。如果存在,则返回 t 所在的下标,否则返回 -1。

注:从下标 0 开始。

输入格式

第一行,n 和 m

第二行,数组 a 的 n 个元素

接下来 m 行,每行一个查找目标值 t

输出格式

一共 m 行,每行 是 t 的查找结果。如果找到 t,则输出 t 在 a 中的下标;否则,输出 -1

样例

示例 1:

输入:

6 2
-1 0 3 5 9 12
9
2

输出:

4
-1

解释: 9 出现在 a 中并且下标为 4。
2 不存在 a 中因此返回 -1

数据范围与提示

50%数据:1<=n,m<=10000

100%数据:1<=n,m<=100000,数组 a 中的所有元素是不重复的。