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) 并且被认为是非常低效的。

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