1. 概要

このチュートリアルでは、並べ替えられて回転された配列で数値を検索する方法について説明します。 問題を定義し、それを説明するための例を提供します。

その後、それを解決するためのエレガントなアプローチを紹介します。

2. 問題の定義

整数、、および個別の整数で構成されるソートされた回転配列、が与えられた場合、私たちのタスクは、値が。に等しい要素の位置を見つけることです。 そのような要素がない場合は、を返します。

次の例を見てみましょう。

与えられた配列で次の番号を見つけたいと仮定します。

  • 位置=0
  • 位置=-1（見つかりません）
  • 位置=3

3. 二分探索アプローチ

3.1. 本旨

主なアイデアは、の位置を見つけるために二分探索技術を使用することです。現在、位置の値を調べている場合、3つの異なるケースが発生します。

  1. ：は、ターゲットを見つけ、その位置を返すことを意味します
  2. ：これは、より大きな要素を探す必要があることを意味するため、左端の要素が、より大きく、ターゲット以下であるかどうかを確認します。 この場合、ターゲットは左端の要素の後に来る必要があります。 したがって、配列の左側にある可能性があります。 そうでなければ、それは正しい部分にあるはずです。
  3. ：それは私たちがより小さな要素を探さなければならないことを意味します。 したがって、右端の要素が、未満であり、以上であるかどうかを確認します。 もしそうなら、私たちのターゲットは右端の要素の前に来るはずです。 したがって、の右側にあります。 それ以外の場合は、左側にあるはずです。

最終的に、バイナリ検索を終了し、検索中に値を返さない場合、ターゲットはに存在しません。 その結果、を返します。

3.2. アルゴリズム

実装を見てみましょう：

実装では、セクション3.1で説明されている正確なアイデアを使用します。

このアルゴリズムの複雑さはです。ここで、は指定された配列の長さです。 この複雑さの背後にある理由は、バイナリ検索の複雑さと同じです。ここでは、指定された配列を毎回2つに分割し、そのうちの1つでターゲットを探し続けます。

4. 結論

この記事では、ソートされた回転配列で整数を見つける最も効率的な方法を紹介しました。 まず、問題の例を示しました。 次に、それを解決するためのエレガントなアプローチを提供し、その実装について説明しました。