algorithm - 查找集合中下一个最小和最大数字的快速算法

Question

我有一组正数。给定一个不在集合中的数字，我想找到集合中 的下一个最小和下一个最大的数字。我现在能想到的唯一方法是通过减 1 来找到下一个最小的，直到我在集合中找到一个数字，然后做同样的事情来找到下一个最大的。

动机:我在 HashMap 中有一堆数据，按日期键控。我没有每个日期的数据点。如果我有数据，比如 10/01/2000 为 60，10/05/2000 为 68，我要求 10/02/2000，我想线性插值。我应该得到 62。

Answer 1

这取决于你的集合是否排序。

如果您的集合未排序，那么找到最接近的(更高和更低)是一个 O(n) 操作和一个相当简单的算法。

如果您的集合已排序，那么您可以使用修改后的二分搜索在 O(log n) 中找到答案，这显然要好得多，尤其是对于较大的集合。

如果您重复执行此操作，则可能值得对集合进行排序，这会产生 O(n log n) 成本，该成本可能一次性或不重复，具体取决于集合更改的频率。随着新项目的添加，某种树排序可能有助于改进 future 的排序。