c# - 查看一组实数的快速方法

Question

我在 C# 4.0 中工作，但遇到以下问题:

给定实数的有限集 S 和参数 k(不一定在集合中)，找到S 中大于或等于 k ​​的最小数。

显然，我可以使用平衡二叉树来做到这一点。但是，在 C# 中没有这种数据结构的实现可以帮助我。算法的选项和 C# 中可能的实现是什么？

编辑:

由于大多数人对批评比真正帮助更感兴趣，我将解释更多:

它适用于将实函数分成数百万个部分(或 bin，如直方图)的算法，我需要找到包含 k 的部分以及在其中应用一些计算的有效方法。这些片段是 [a; b) 并且不要重叠。

我正在设计的方法需要在给定 k 的情况下取件，并且对性能至关重要，因为它应该每秒调用数千次。因此，O(n) 搜索是 Not Acceptable 。

构建 S 的数据结构所花费的时间并不重要也不重要，因为该集合只会构建一次并且永远不会改变(它是一个不可变的集合)。

我知道我可以使用具有 O(log n) 搜索复杂度的红黑树。但是，我想研究其他算法选项(可能还有 C# 中的现有实现)。

Answer 1

最简单的方法是 (O(N)) :

double k = 3.5;
List<double> S = new List<double>() { 1, 3, 5, 7, 9, 2, 4, 5, 6, 8, 10 };

var min = S.Where(f => f >= k).Min(); //4

---

如果您的列表已经排序，那么成本是 O(LogN)

List<double> S = new List<double>() { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

var index = S.BinarySearch(k);
var min = index > 0 ? S[index] : S[~index];