Problem: 查找第一个大于等于x的位置

任务总览

题目描述

请在一个有序不递减的数组中（即数组中的值可以相等），采用​二分查找​，找到第一个大于或等于元素 x 的位置。如果不存在这样的元素，请输出 -1。

本题需要处理多个查询，给定 q 个查询数 x，对于每个 x，找出数组中第一个大于等于 x 的元素的位置。

注意：位置从 1 开始计数。

例如，有 6 个数：1 2 2 2 6 6，要查询的 3 个数为：5 8 2，答案应为：5 -1 2。

输入格式

• 第一行：一个整数 n $(1 ≤ n ≤ 10^5)$，表示数组的元素个数。
• 第二行：n 个整数，表示数组的元素，满足非递减排列（$1 ≤ a\_i ≤ 10^8$）。
• 第三行：一个整数 q $(1 ≤ q ≤ 10^5)$，表示要查询的次数。
• 第四行：q 个整数，表示要查询的每一个目标值 x（$1 ≤ x ≤ 10^8$）。

输出格式

• 输出 q 个整数，分别表示每个查询的答案。若存在满足条件的元素，输出其在数组中的​最小位置​（从 1 开始）；否则输出 -1。多个答案以空格分隔。

输入输出示例

输入示例

6
1 2 2 2 6 6
3
5 8 2

输出示例

5 -1 2

题目解析

• 本题核心在于使用二分查找找到第一个满足 a[i] ≥ x 的位置。
• 数组有重复值，所以不能直接返回等于 x 的位置，而是要返回​最靠前的符合条件的位置​。
• 二分查找的时间复杂度为 $O(\log n)$，对于 $q$ 次查询，总体复杂度为 $O(q log n)$，可接受。