二分3：找前驱后继问题
题面分析
本题要求在一个已升序排列的数组中，对于每一个给定的目标值 target，找到数组中比 target 小的最大值 max_val 和比 target 大的最小值 min_val。若不存在满足条件的值，则相应地输出 -1。
思路
从前驱和后继的定义入手:
- 前驱: 从数组
arr 中所有小于 target 的元素中找到最大值 max_val。即第一个比 target 小的数。
- 后继: 从数组
arr 中所有大于 target 的元素中找到最小值 min_val。即第一个比 target 大的元素。
这么一看，似乎与上一题所用到的 bisect_left和 bisect_right 有联系。
我们先来分析 前驱，即第一个比 target 小的数。
我们可以分两种情况来处理：
- 如果数组中存在
target 这个数，因为数组是升序的，所以第一个等于 target 的数的前一个数就是 target 的前驱。
- 如果数组中不存在
target，那么第一个大于 target 的数的前一个位置的数就是 target 的前驱。
通过分析可得，不论哪种情况，我们都可以通过找到第一个大于等于 target 的数来确定 target 的前驱，而这个正好可以通过 bisect_left 函数来实现。
pos_max = bisect.bisect_left(arr, target) - 1
而判断前驱是否存在的条件就是 pos_max 是否在数组的范围内：
max_val = arr[pos_max] if pos_max >= 0 else -1
再来分析 后继:
我们要找到第一个大于 target 的位置，这正是 bisect_right 函数的功能。因此直接使用 bisect_right 函数即可：
pos_min = bisect.bisect_right(arr, target)
同样地，我们需要判断 pos_min 是否在数组范围内：
min_val = arr[pos_min] if pos_min < n else -1
代码实现（Python）
import bisect
def main():
# 输入
n, Q = map(int, input().split()) # n为数组大小，Q为查询次数
arr = list(map(int, input().split())) # 输入升序数组
# 处理每个查询
for _ in range(Q):
target = int(input()) # 输入目标值
# 查找比 target 小的最大值
pos_max = bisect.bisect_left(arr, target) - 1
max_val = arr[pos_max] if pos_max >= 0 else -1
# 查找比 target 大的最小值
pos_min = bisect.bisect_right(arr, target)
min_val = arr[pos_min] if pos_min < n else -1
# 输出结果
print(max_val, min_val)
if __name__ == "__main__":
main()
题目描述：
给定一个升序排列的数组 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
