performance - 在数字范围列表中搜索数字

Question

假设有一个数字范围列表，例如 {0,9},{14,18},{19,30}。

我想确定一个数字 N 是否在列表中。如果 N=15 ，答案将是肯定的，因为 15 在 {14,18} 范围内 如果 N=11 ，答案将为否，因为 11 不在列表中的这些范围内。

我的问题是：是否有任何有效的方法来确定此类问题的答案？

谢谢

Answer 1

如果您对范围列表进行排序，然后加入重叠范围，则可以通过二分搜索解决您的问题，即 O(log(N))，其中 N 是列表中的元素数。

对范围进行排序和连接后，您可以将范围列表放入一个数组中，例如 { a, b }, { c, d } 将变为 ( a, b, c, d )，然后在二分查找之后可能会检查您的号码是否在具有偶数和奇数位置的元素之间，然后您的号码在范围内，否则它就出局了。

二进制搜索是您有一个排序数组的地方，因此您可以将数组分成两个相等的部分，并将您的键值与数组值进行比较，将部分分开，然后选择上部或下部进行一次又一次划分。

如果您不使用二进制搜索，并且您的列表未排序，则每次都必须查看所有元素，这 O(N) 并且被认为是非常低效的。

如果您需要更详细的解释，请发表评论。

Answer 2

如果范围列表动态变化，那么区间树就是您要查找的数据结构。