C++の非常に大きな配列を特定の値で検索するには？

Question

私はインタビュアーによってこの質問をしました。特定の値に対して大きな配列（数千万の値）を検索するにはどうすればよいですか。

アイテムがソートされ、配列サイズが小さい場合はバイナリ検索をお勧めします。大規模な配列（値が1回のパスの右端にある）に最大の値が必要な場合は、バブルソートアルゴリズムの1回の反復を提案しました。

しかし、私はどのアルゴリズムが本質的にランダムな配列インデックス内の値を抽出できるかは不明です。

Answer 1

1. リニア検索。これにはO(n)が必要です。アレイのサイズが数千から数百万の範囲であれば十分です。

2. 検索操作をより頻繁に行う場合。配列をハッシュテーブルに変換したい場合があります。ハッシュテーブルの構築には最初にO(n)が使われ、すべての検索操作はO(1)になります。あなたが行うすべての検索操作に対して、ソリューション1はO(n)となります。

3. アレイが本当に大きい場合は、複数のスレッドを利用してアレイを同時に検索できます。配列を部分に分割し、各スレッドはその部分の値を検索します。

Answer 2

標準的なリニア検索です。最初から始め、最後まで検索します（最悪の場合）。

要素の順序付けに関する保証がない場合は、すべての要素を確認する必要があります。つまり、あなたが望むことができる最高の複雑さはO（n）です。これらの条件の下では、これは配列のサイズに関係なく答えになります。