中等题:二分查找+模拟
[[3,4],[2,3],[1,2],[5,6],[10,12]]
对于当前区间[3,4]
,找一个最贴近它的右侧区间([5,6],[10,12]
),为[5,6]
二分查找的特征:
- 最多有2e4个区间,所以可以使nlogn,如果2e8,显然二分查找就不再适用了。
- 明显的“比较”特征;
逻辑:
- 对于[3,4]
- 找到大于等于4的最小左边界
- [1,2,3,5,10]上,找大于等于4的左边界
- 注意等号,要用bisect_left();具体的边界情况可以查看函数注释。
bisect_left(): The return value i is such that all e in a[:i] have e < x, and all e in a[i:] have e >= x.