Problem: 最后一次出现的位置（二分）

任务总览

题目描述

请在一个有序不递减的数组中（数组中的值可能相等），使用​二分查找​，找到每个给定数字 x 在该数组中​最后一次出现的位置​。

如果数组中不存在 x，请输出 -1。

注意：下标从 1 开始计数。

例如，数组为：

1 2 2 2 3 3

如果要查找的数字是 3 2 5，则对应的最后一次出现的位置为：

6 4 -1

输入格式

• 第一行包含一个整数 n $(1 ≤ n ≤ 10^5)$，表示数组中元素的个数。
• 第二行包含 n 个按非递减顺序排列的正整数，表示数组元素。
• 第三行包含一个整数 q $(1 ≤ q ≤ 10^5)$，表示需要查找的位置查询数。
• 第四行包含 q 个正整数，表示要查找的 x 值。

输出格式

• 输出 q 个整数，用空格分隔，分别表示每个 x 在数组中​最后一次出现的位置​，如果 x 不存在，输出 -1。

输入输出示例

输入示例 1

6
1 2 2 2 3 3
3
3 2 5

输出示例 1

6 4 -1

题目解析

• 本题要求对一个非递减数组进行多次查找，可以使用二分查找来高效定位每个值 x 最后一次出现的位置。
• 具体做法是：对每个查询值 x，使用二分查找找到它在数组中​最右侧的位置​，即满足 a[mid] == x，且是最后一个满足条件的下标。

数据范围

• 数组长度 n 和查询次数 q 最多为 $10^5$
• 数组元素值和查询值均不超过 $10^8$