在 .NET/C# 上下文中，什么是二分搜索以及如何/为什么使用二分搜索？

Question

我今天第一次在维基百科上读到有关二分搜索的内容，只是粗略地浏览了一下。它似乎用于在内存稀疏的情况下快速查找集合中的项目。

在 .NET/C# 环境中，我是否需要使用它？您在构建实际的生产软件时使用过它们吗？

如果这个问题听起来很煽动，我很抱歉，但我作为一名学生问的是一个真实的问题！

Answer 1

List 有一个 BinarySearch方法，Array 也是如此。如果您有一个排序列表并且需要查找一个元素，您将使用它们。因为它们返回一个索引，所以您可以完成使用直接字典无法完成的操作，例如查找小于键的最大元素。

我在现实软件中使用二分搜索的一个地方是进行范围搜索。运费是根据重量范围给出的，因此 0-1 磅可能有一种费率，1-5 磅有一种费率，5-10 磅有一种费率。如果我调用 List.BinarySearch 并查找 4 磅，它会给我第一个高于 4 磅的索引，我可以使用它来查找 1-5 磅范围。字典只会告诉我没有找到 4 磅。

对于一般排序数据，您通常最好使用 SortedList 或 < a href="http://msdn.microsoft.com/en-us/library/f7fta44c.aspx" rel="nofollow noreferrer">排序字典。

Answer 2

二分搜索仅适用于排序数据，因此只要您在 C# 中有一些已知已排序的数据集合，就可以对其进行二分搜索。您最好的选择是使用已提供的实现（例如 List.BinarySearch()），但如果您使用的特定集合没有二分搜索方法，你总是可以写一个。

下面是一个使用内置库的示例：

// An ordered list of ints
List<int> ints = new List<int>() { 1, 4, 8, 20, 30, 44 };

// Search for 5 in the list
int ix = ints.BinarySearch(8);

// Display the index the element 8 was found at
Console.WriteLine(ix);

是的，当您搜索排序数据时，您肯定会希望使用二分搜索。

Answer 3

不久前（当我还是计算机工程课程的学生时）我必须使用搜索算法。这种课程作业的结果就是一篇论文。

我在我的博客上发布了关于 快速排序和二分搜索算法C++。虽然它是 C++ 代码，但它应该为您提供如何/为什么使用二分搜索。它还展示了如何实现二分搜索算法。提供了一个示例应用程序，以便您可以自行测试。