Search Rotated Array
任意の数だけ右へ回転されたソート済み配列と、指定された数（key）が渡されて検索します。
説明
任意の数だけ回転されたソート済み配列で、指定された数(key)を検索します。 Keyが存在しない場合は-1を返します。 配列に重複が含まれていないと仮定します。
以下は、回転前の元の配列です。
この配列で6回、回転を実行すると、次のように変わります。
条件
- 線形検索O(n)は受け入れられない解決策です。
- 修正したBinary Searchを考える。
Solution
Runtime Complexity O(logn)
Binary Search を利用している。
Memory Complexity O(logn).
一回のループごとに、渡されたArrayを半分に切って、片方のみに検索をかけている。
解説
解決策は、基本的にBinary Search ですが、いくつかの修正が加えられています。 例の配列をよく見ると、配列の少なくとも半分が常にソートされていることがわかります。 この特徴を利用します。 探している数値nが配列のソートされた半分の中にある場合は、Binary Search で見つけることができます。 それ以外の場合は、ソートされた半分を破棄し、ソートされていない半分を調べ続けます。 各ステップで配列を半分に分割しているため、これによりRuntime Complexity はO（logn）となります。
コードにおいて、少し読みにくい条件分けの部分があります。四つの条件で
1. 半分に切ったstart ~ mid の範囲のSubArrayがソートされている、かつ、探しているKeyがその範囲に存在するとき。
2. 半分に切ったmid ~ end の範囲のSubArrayがソートされている、かつ、探しているKeyがその範囲に存在するとき。
3. 半分に切ったstart ~ mid の範囲のSubArrayがソートされてなく、かつ、探しているKeyがその範囲に存在するとき。
4. 半分に切ったmid ~ end の範囲のSubArrayがソートされてなく、かつ、探しているKeyがその範囲に存在するとき。
と言う様に条件分けしています。
実装
テスト
アウトプット
