【二分3】找前驱后继问题
题解
题面分析
本题要求在一个已升序排列的数组中，对于每一个给定的目标值 target，找到数组中比 target 小的最大值 max_val 和比 target 大的最小值 min_val。若不存在满足条件的值，则相应地输出 -1。
思路
题目描述：
给定一个升序排列的数组 arr，长度为 n，以及 Q 次询问。每次询问都会给出一个目标值 target。对于每个目标值，请找出数组中比目标值小的最大值 max_val 和比目标值大的最小值 min_val。
具体而言，要求对于每个询问：
- 从
arr 所有小于 target 的元素中找到最大值 max_val。
- 从
arr 所有大于 target 的元素中找到最小值 min_val。
如果不存在比 target 小的值，则 max_val 输出为 -1；如果不存在比 target 大的值，则 min_val 输出为 -1。
输入：
- 第一行包含两个整数
n 和 Q，表示数组的长度和询问的次数。
- 第二行包含
n 个升序排列的整数，表示数组 arr。
- 接下来的
Q 行中，每行包含一个整数 target。
输出：
对于每个询问，输出一行，包含两个整数 max_val 和 min_val，分别表示比 target 小的最大值和比 target 大的最小值。
数据范围：
- 1≤n,Q≤105
- 1≤arr[i]≤109 （数组中的元素为正整数且升序排列）
- 1≤target≤109
样例输入：
5 3
1 3 5 7 9
4
6
10
样例输出：
3 5
5 7
9 -1
