1894 - 二分查找左侧边界

题目描述

请在一个有序不递减的数组中(数组中有相等的值),采用二分查找,找到值 xx11 次出现的位置,如果不存在 xx 请输出 1-1

请注意:本题要求出 qqxx ,每个 xx 在数组中第一次出现的位置。

比如有 66 个数,分别是:11 22 22 22 33 33,那么如果要求 33 个数:33 22 55,在数组中第一次出现的位置,答案是:55 22 1-1

输入

第一行,一个整数 nn,代表数组元素个数(n105n \le 10^5

第二行,nn 个整数,用空格隔开,代表数组的 nn 个元素(11 \le 数组元素的值108 \le 10^8

第三行,一个整数 qq,代表有要求出 qq 个数首次出现的位置(q105q \le 10^5

第四行,qq 个整数,每个数字占一行,代表要找的数(11 \le 要找的数108 \le 10^8

输出

输出 11 行,含 qq 个整数,按题意输出要找的每个数在数组中首次出现的位置,如果不存在这样的数,请输出 1-1

样例

输入
复制

6
1 2 2 2 3 3
3
3 
2 
5

输出
复制

5 2 -1
说明

【注意】

由于本题读入、输出的数据较多,C++选手请使用scanfprintf 替代 cincout 提升读写效率。

来源

二分 分治

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 17
通过人数 8
金币数量 1 枚
难度 入门


上一题 下一题