快速检查一个非常大的数组中是否存在数字（C#）

Question

玩编码游戏教程时遇到问题。目标是检查数组int中是否存在。int问题是，教程有这个要求：该解决方案在合理的时间内适用于一百万个项目我尝试了许多不同的方法，如 LINQ、Dictionary二进制搜索、指数搜索和其他一些方法，但仍然失败。谁能告诉我解决这个问题的最快方法？

Answer 1

在任意数组中查找一个数字将不可避免地花费O(N)（与输入呈线性关系）时间（因为您无法对任何给定索引上的内容做出任何假设，因此您只需要在最坏的情况下访问它们即可）。

对数组进行排序后，情况会有所改善——在这种情况下，您可以使用二分搜索及时找到值O(log n)。这是内置的 .NET 使用Array.BinarySearch方法。如果您只需要搜索一次值，这是最好的解决方案。

if ( Array.BinarySearch(data, number) >= 0 )

{

   //found

}

最后，您将多次搜索数组，更好的选择是首先HashSet<int>从数组中创建一个。在这种情况下，任何后续查询都将以平均O(1)时间（常数）返回。但是，在这种情况下，您需要记住，创建HashSet<int>遗嘱本身需要O(n)时间和记忆。仅当系统要求您多次搜索该值时，此解决方案才值得使用。如果你只搜索一次，那么你最好只遍历一次数组，这样O(N)你也可以节省内存。

var lookup = new HashSet<int>(data);

if ( lookup.Contains(number) )

{

   //do something

}