二分查找

题目描述

给定一个长度为 n 的升序排列整数数组 a，以及 m 个查询数字。对于每个查询数字 x，请判断它是否存在于数组中。如果存在，输出它在数组中的位置（从 1 开始）；如果不存在，输出 -1。

输入格式

第一行包含两个整数 n 和 m，分别表示数组长度和查询次数。

第二行包含 n 个整数，表示升序排列的数组 a。

接下来 m 行，每行一个整数 x，表示要查询的数字。

输出格式

对于每个查询，输出一行一个整数，表示查询结果。

样例

样例输入

5 3
1 3 5 7 9
3
4
9

样例输出

2
-1
5

样例解释

• 查询 3：数组中第 2 个元素是 3，输出 2
• 查询 4：数组中不存在 4，输出 -1
• 查询 9：数组中第 5 个元素是 9，输出 5

数据范围

• 1 <= n, m <= 10^5
• -10^9 <= a[i], x <= 10^9
• 数组 a 保证升序排列
• 时间限制：1秒
• 内存限制：256MB

提示

使用二分查找算法可以在 O(log n) 时间内完成单次查询。