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

Question

我今天第一次在 Wikipedia 上阅读了二进制搜索，只是略略略过表面。它似乎用于在内存稀疏的集合中快速查找项目。

在 .NET/C# 上下文中，我是否需要使用一个？您是否曾经在构建生产型真实世界软件时使用它们？

如果这个问题被认为是煽动性的，我很抱歉，但我作为学生提出了一个真正的问题！

Answer 1

List<T>有一个BinarySearch方法，就像Array一样。如果你有一个排序列表并且需要找到一个元素，你会使用它们。因为它们返回一个索引，所以你可以做一些你不能用直接字典做的事情，比如找到小于键的最大元素。

我在实际软件中使用二进制搜索的一个地方是进行范围搜索。运费是根据重量范围给出的，所以可能有一个 0-1 磅的运费，一个 1-5 磅的运费，一个 5-10 磅的运费。如果我打电话List<T>.BinarySearch找 4 磅，它会给我第一个指数高于 4 磅，我可以使用它找到 1-5 磅的范围。字典只会告诉我找不到 4 磅。

对于一般排序数据，您通常最好使用SortedList或SortedDictionary。

Answer 2

二进制搜索仅适用于已排序的数据，因此只要您在 C# 中有一些您知道已排序的数据集合，您就可以对其进行二进制搜索。您最好的选择是使用已经提供的实现（例如List<T>.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++ 代码中，但它应该为您提供如何/为什么使用二进制搜索。它还展示了如何实现二进制搜索算法。提供了一个示例应用程序，您可以自己测试它。