在.NET/C环境中,什么是二进制搜索以及如何/为什么可以使用它?

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

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

对于一般排序的数据,最好使用 SortedList 或 SortedDictionary .

二进制搜索只对排序后的数据起作用,只要您在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);

是的,在搜索排序的数据时,您肯定希望使用二进制搜索。

前一段时间(我是计算机工程专业的学生),我不得不学习搜索算法。这门课程的结果是一篇论文。

我在博客上发表了关于 Quicksort and Binary Search algorithms in C++ . 虽然它是C++代码,但它应该为你提供 如何/为什么 使用二进制搜索。文中还介绍了如何实现二进制搜索算法。提供了一个示例应用程序,以便您自己测试它。