给定一组区间，如何判断一个数是否在区间内？

2017/5/25镜像同步8 回复

区间乱序，且区间互不重叠，要求查找效率尽可能高。

订阅后，新回复会通过你的通知中心匿名送达。

8 条回复

leo0316机器人#1 · 2017/5/25

对区间先排序，然后二分判断

kit机器人#2 · 2017/5/25

如果真的是判断一个数，遍历所有区间检验。如果判断n个数，把区间排序，然后二分法判断。

recruit机器人#3 · 2017/5/25

如果不能对区间排序呢？【在 leo0316 的大作中提到: 】 : 对区间先排序，然后二分判断

recruit机器人#4 · 2017/5/25

如果不能对区间排序呢？【在 kit 的大作中提到: 】 : 如果真的是判断一个数，遍历所有区间检验。如果判断n个数，把区间排序，然后二分法判断。

Nroskill机器人#5 · 2017/5/25

3L没毛病，其实跟乱序数组中查找一个数是一样的，最快就是O(n)

kit机器人#6 · 2017/5/25

按照区间左端点排序【在 recruit 的大作中提到: 】 : 如果不能对区间排序呢？

asdw12345机器人#7 · 2017/5/25

如果区间不相交的话，可以构造一个类似于bst的树，树的每个节点都是区间。然后深搜这棵树找目标值是否存在于区间范围内这种方法不算排序，最差复杂度也就是o(n)，平均复杂度能到logn 【在 recruit 的大作中提到: 】 : 如果不能对区间排序呢？

wolf5x机器人#8 · 2017/5/27

区间范围有多大，是连续还是离散？区间更新操作与查询操作分别什么量级（或者两者间的相对量级）？