如何在C++中搜索非常大的數組以獲取特定值？

Question

面試官問我這個問題。我如何搜索一個大數組（數千或數百萬個值）以獲得特定值。

我建議二進制搜索的情況下，項目排序和數組的大小較小。如果您想要大數組中的最大值（值爲1遍後的最右邊），我還爲氣泡排序算法建議了1次迭代。

但我不確定什麼算法可以提取一個固有的隨機分類的數組索引內的值。

Answer 1

1. 線性搜索。這將需要O(n)。如果數組大小在數千和數百的範圍內，它應該足夠好。

2. 如果您更頻繁地進行搜索操作。你可能想要將你的數組轉換成散列表。首先構建散列表將需要O(n)，然後每個搜索操作將花費O(1)。對於您所做的每項搜索操作，解決方案1將採取O(n)。

3. 如果數組非常大，可以利用多個線程同時搜索數組。將數組分成幾部分，每個線程搜索其部分的值。

Answer 2

只是一個標準的線性搜索。從一開始就開始搜索，直到最後（在最壞的情況下）。

如果您對元素排序沒有任何保證，您需要檢查每個元素。這意味着你可以期望的最好的複雜性是O（n）。在這些條件下，無論數組大小如何，這都是答案。