2313. 星际档案库的“快速定位”任务
1000ms
256MB
简单
二分算法
题目描述
在星际联邦的中央档案库中，存放着一份包含 $n$ 个绝密档案编号的清单。为了确保查询效率，这些编号已经按照**从小到大**的顺序（严格递增，无重复元素）排列好了。
档案管理员哈利收到了一项紧急任务：给出一个目标编号 $x$，他需要快速找出这个编号在清单中的**索引位置**（索引从 1 开始计数）。如果清单中根本没有这个编号，哈利必须立刻上报并输出 -1。
由于档案数量庞大（最高可达 $5 \times 10^6$），哈利必须使用最高效的**二分查找法**来完成定位，否则就会因为超时而无法通过考核。
输入格式
- 第一行：一个整数 $n$ ($n \le 5 \times 10^6$)，代表清单中档案编号的总个数。
- 第二行：$n$ 个正整数，代表清单中已排好序的递增编号 ($1 \le \text{编号值} \le 10^8$)。
- 第三行：一个整数 $x$ ($0 \le x \le 10^8$)，代表哈利需要查找的目标编号。
输出格式
- 输出一个整数，表示目标编号 $x$ 在清单中的位置（从 1 开始编号）；如果不存在，则输出 -1。
样例 1
输入 (Input)
10 1 3 5 7 9 11 13 15 17 19 3
输出 (Output)
2
- 对于所有数据：$n \le 5 \times 10^6$。
- 清单内的编号严格递增，不存在相同元素。
- **性能提示**：
由于数据量高达 $5 \times 10^6$，线性查找（遍历）会产生 $O(n)$ 的开销，必然导致超时（TLE）。必须使用时间复杂度为 $O(\log n)$ 的二分查找算法。
- **I/O 优化提示**：
在大数据量下，C++ 的 `cin` 和 `cout` 效率较低，建议在 `main` 函数开头加入 `ios::sync_with_stdio(false); cin.tie(0);` 来加速读入过程。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功