ソート済み配列 - アルゴリズムとデータ構造 | ++C++; // 未確認飛行 C

概要 コレクションを使う際、 要素の並び順には意味がない場合があります。 例えば、辞書のような用途を考えてください。 辞書の中に要素が含まれているかを検索できればそれでよくて、 要素が挿入された順序などはあまり意味がありません。 一般に、「配列リスト」等の、順序構造を保つコレクションを使った場合、 コレクション中に要素が含まれているかどうかを検索するのには、 要素数 n に比例した計算量（O(n)）が必要です。 しかしながら、（挿入された順序を保てない代わりに）要素の検索に特化したコレクションを使うことで、 高速に（計算量 O(log n) で）検索が可能です。 例えば、単なる配列（あるいは「配列リスト」）であっても、 常にソート済みに保っておくならば、 2分検索法という高速な検索アルゴリズムが適用できます。 ここで説明するソート済み配列（sorted array）は、 その2分検索法を使