ソートされていない配列内で前後方向に検索

未ソート配列 - 配列は、同じ型の要素のコレクションで構成されるデータ構造です。ソートされていない配列は、要素の順序がランダムな構造です。つまり、挿入時に、要素は前の要素の順序に関係なく最後の要素に追加され、そのような配列での検索には検索アルゴリズムの支援が適用されません。要素の配置パターンが欠如しているためです。

検索 - 配列内の検索とは、配列内の特定の要素を見つけることを意味します。これにより、目的の要素の位置、または要素が配列内に存在するかどうかを指定するブール ステートメントを返すことができます。

• 前方検索 - 配列の前方検索とは、0 番目のインデックス (つまり、最初の要素) から始まる配列の線形検索トラバーサルを実行することを意味します。

• 逆検索 - 配列の逆検索とは、(n-1) 番目のインデックス (つまり、最後の要素) から始まる配列の線形検索を意味します。

＃＃＃問題文＃＃＃

検索要素 x が与えられた場合、次の状況で x が存在するかどうかを調べます -

同じサイズの要素を含む配列、整数配列。
異なるサイズの要素を含む配列、文字列配列。
例 1

リーリー リーリー

説明

- 指定された配列では、2 番目のインデックスに 4 が発生します。 例 2

リーリー リーリー

説明

- 指定された配列には、「high」が存在しません。 ＃＃＃解決＃＃＃ 上で述べたように、前方検索は最初の要素から開始され、後方検索は最後の要素から開始されます。これら 2 つの方法を組み合わせると、配列の前半と後半が同時にチェックされるため、配列内の要素の検索時間を 2 倍に短縮できます。

要素が配列内に存在するかどうかを確認するには、first と last を配列の最初と最後の要素として定義します。最初または最後の要素が必須要素である場合は true を返し、それ以外の場合は最初の要素を 1 ずつインクリメントし、最後の要素を 1 ずつデクリメントし、要素が見つかるまで処理を続けます。走査完了時に first と last が等しい場合、要素が見つからなければ false が返されます。

疑似コード

リーリー

例: C 実装

次のプログラムでは、整数配列の最初のケースを取り上げます。最初と最後の要素をチェックしながら最初と次の変数を取得し、必要な要素を見つけます。要素が見つかった場合は true を返し、見つからない場合は次の要素に移動して再度確認します。

リーリー ＃＃＃出力＃＃＃ リーリー

時間計算量 - O(n/2)、両側から検索することで時間が半分に短縮されます。

空間の複雑さ - O(1)

＃＃＃例＃＃＃

次のプログラムでは、文字列配列の 2 番目のケースを使用します。最初と最後の要素をチェックしながら最初と次の変数を取得し、必要な要素を見つけます。要素が見つかった場合は true を返し、そうでない場合は次の要素に移動して再度確認します。

リーリー ＃＃＃出力＃＃＃ リーリー

時間計算量 - O(n/2)、両側から検索することで時間が半分に短縮されます。

空間の複雑さ - O(1)

＃＃＃結論は＃＃＃

つまり、配列の前方検索と後方検索は通常の線形検索と似ていますが、2 つの要素を同時にチェックするため、消費時間が半分になる点が異なります。これにより、ソートされていない配列での検索の最悪の場合の時間計算量が O(n) から O(n/2) に変換されます。

以上がソートされていない配列内で前後方向に検索の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。