ソートおよび回転された配列内の要素を検索する C++ プログラム

点を中心に回転されたソートされた配列が得られます。配列内を検索するためのキーも取得します。この回転された配列内の要素を検索するために使用されるロジックは -

です。

• まず、配列の中央の要素を見つけます。キーが存在する場合は、キーが配列内に存在することを返します。

• キーが中央にない場合は、配列の左側の部分 (左から中央) がソートされているかどうかを確認できます。ソートされている場合は左側のキーを探すことができ、ソートされていない場合は右側 (中央 1、右) のキーを探すことができます。

キーが中央で見つからず、左側の部分がソートされていない場合は、右側の部分をソートして、右側の部分にキーが存在するかどうかを確認します。そうでない場合は、検索します。配列の左側の部分を右側の部分に配置します。

• それ以外の場合は、見つからないことを返します。

• 以下でいくつかの入出力シナリオを見てみましょう -

その要素で構成される配列があると想像してください。たとえば、2、5、7、9、11 は、回転後、5、9、11、2、7 になります。配列キーが 2 であるとします。 リーリー キーが指定された配列にない別のシナリオを想定してみましょう。

リーリー ＃＃＃アルゴリズム＃＃＃

次の手順は実装方法です。

配列の中央の要素を見つけます。

配列を 2 つの部分に分割します。 (中央 = 左右) / 2
key が中間要素かどうかを確認します。
Else if は、配列の左側の要素をチェックし、ソートされます
そうでない場合は、右の要素 (中央 1、右) をチェックしてください
それ以外の場合は、左側の部分を並べ替えて

• を確認してください

それ以外の場合は、要素が見つからないことを返します。

• ＃＃＃例＃＃＃
たとえば、配列「2,3,4,5,6,7,8」があり、回転された配列が「5,6,7,8,2,3,4」であるとします。この配列のキーは 2 です。

• この操作の C 実装は次のとおりです -

  リーリー ＃＃＃出力＃＃＃ リーリー ＃＃＃結論は＃＃＃
この問題を解決するもう 1 つの方法は、配列の回転のピボット ポイントまたはインデックスを見つけて、エッジの二分探索を実行することです。私たちの方法では、問題を解決するために 1 回の二分探索のみが必要です。配列の検索や並べ替えを見るときは、検索方法の 1 つとして二分検索を考慮する必要があります。

以上がソートおよび回転された配列内の要素を検索する C++ プログラムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。