Skip to content

中等题:二分查找+模拟

436. 寻找右区间

[[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.