1305 : 二分查找

时间限制Time Limit
1 秒Sec
内存限制Memory Limit
128 兆MB
提交次数Submitted
783 次Times
通过次数Solved
216 次Times

题目描述Description

在给出的有序数组中查找特定数值的 Lower Bound 和 Upper Bound,在有序数组中,它们的定义分别是:

  • Lower Bound:对于给定的元素 \(x\),不小于 \(x\) 的第一个元素的位置
  • Upper Bound:对于给定的元素 \(x\),大于 \(x\)的第一个元素的位置

输入格式Input

第一行 \(1 \leq n \leq 10^7\) 与 \(1 \leq m \leq 100\),表示 \(n\) 个元素的有序数组 \(a\) 和 \(m\) 次查询.

数组由如下代码定义:

for(int i = 0; i < n; i ++) {
    a[i] = (i == 0 ? 0 : a[i - 1]) + (int)(100 * sin(n + i)) % 3;
}

接下来 \(m\) 行每行一个整数表示查询的 \(x\).

输出格式Output

对于每个查询,输出空格隔开的 Lower Bound 和 Upper Bound 的数组下标,如果对应内容不存在则输出 -1.

样例Sample

出题Author

CSGrandeur