如何在C++中搜索非常大的数组以获取特定值？

Question

面试官问我这个问题。我如何搜索一个大数组（数千或数百万个值）以获得特定值。

我建议二进制搜索的情况下，项目排序和数组的大小较小。如果您想要大数组中的最大值（值为1遍后的最右边），我还为气泡排序算法建议了1次迭代。

但我不确定什么算法可以提取一个固有的随机分类的数组索引内的值。

Answer 1

1. 线性搜索。这将需要O(n)。如果数组大小在数千和数百的范围内，它应该足够好。

2. 如果您更频繁地进行搜索操作。你可能想要将你的数组转换成散列表。首先构建散列表将需要O(n)，然后每个搜索操作将花费O(1)。对于您所做的每项搜索操作，解决方案1将采取O(n)。

3. 如果数组非常大，可以利用多个线程同时搜索数组。将数组分成几部分，每个线程搜索其部分的值。

Answer 2

只是一个标准的线性搜索。从一开始就开始搜索，直到最后（在最坏的情况下）。

如果您对元素排序没有任何保证，您需要检查每个元素。这意味着你可以期望的最好的复杂性是O（n）。在这些条件下，无论数组大小如何，这都是答案。