c# - .net4 BinarySearch 在排序列表中

Question

我想在 c# 4.0 的排序列表上使用二进制搜索选项。我一直在研究旧的二进制搜索：

我将如何使用 C# 搜索一系列范围值

我想要一些关于如何使用 binarySearch 在两个日期之间进行范围搜索的帮助。我有一个包含许多日期的列表，我想在两个日期之间快速搜索这个大列表并返回找到的项目（如果有的话）。我认为二进制搜索会很快，因为它会在排序时迅速摆脱不必要的比较。

Answer 1

假设：

• 你有一个给定类型 T 的集合、有序列表或数组。
• 所述集合是一个袋子（允许重复）而不是一个集合（独特的项目）。

你需要

• 进行二分搜索以找到符合您的“来自”标准的项目，即下限。

  由于这是一个二分搜索，并且您有一个bag而不是set，因此您不能保证这是集合中满足 from 条件的第一个项目。这意味着你需要...

• 备份到与“来自”条件匹配的第一个项目。这是一个顺序操作。

  此时，您有了迭代的起点。您所要做的就是从这一点开始按顺序遍历集合......

• 而“通过”标准，上限条件为真。

这可能建议对上限和下限测试使用自定义比较器。

它还可能以 LINQy 扩展方法的形式提出解决方案。

祝你好运！

Answer 2

假设您的列表是 List 并且您的日期是 DateTime 您可以通过这种方式执行 List.BinarySearch(...)

List<DateTime> l;
int startIndex = l.BinarySearch(beginDate);
int endIndex = l.BinarySearch(endDate);

此时，您已经有了 beginDate 和 endDate 之间的日期范围。现在您可以让它们在两个索引之间进行迭代。

如果您想在未找到确切日期的情况下找到最接近的日期，则无法执行二进制搜索。在这种情况下，您必须重新实现您的数据结构（在您的情况下，您的 List 必须被一些强大的结构替换）以支持由二叉搜索树组成的范围搜索算法，您将在其中存储每年并且每个节点将包含一个新的二叉搜索树，该树将包含属于该年的所有月份，现在每个节点将包含一个新的二叉搜索树，该树将包含该月的所有日期，依此类推。