回転ソート配列での探索
回転ソート配列での探索
このレッスンで分かること
- 毎回区間が半分になるので
O(log n)、空間はO(1)です- 昇順
ソートされた配列を、ある位置でぐるっと回した配列を回転ソート配列と呼びます回転ソート配列を真ん中で割ると、必ず 片側は完全にソート済み になります
回転ソート配列での探索 とは
昇順ソートされた配列がある位置で回転している配列に対し、target の index を O(log n) で探します。
昇順 ソート された配列を、ある位置でぐるっと回した配列を 回転ソート配列 と呼びます。例えば [1, 2, 3, 4, 5] を 2 回転 (左に 2 つシフト) したら [3, 4, 5, 1, 2] です。重複なし で考えるのが定番の問題設定です。
LeetCode 33. Search in Rotated Sorted Arrayとして有名な問題です。O(log n)で解けることが要求されます。
観察
回転ソート配列 を真ん中で割ると、必ず 片側は完全に ソート 済み になります。
例えば [4, 5, 6, 7, 0, 1, 2] を mid=3 (7) で割ると、左側 [4,5,6,7] は ソート 済み、右側 [0,1,2] も ソート 済み。一般化すると、mid を境界にして:
arr[low] <= arr[mid]なら左半分がソート済み- そうでなければ
右半分がソート済み
そして ソート 済みの方に target が範囲内に含まれるかを >= <= でチェックすれば、進むべき方向が決まります。
コード
Python
def rotatedSearch(arr, target):
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
if arr[low] <= arr[mid]: # 左がソート済み
if arr[low] <= target < arr[mid]:
high = mid - 1
else:
low = mid + 1
else: # 右がソート済み
if arr[mid] < target <= arr[high]:
low = mid + 1
else:
high = mid - 1
return -1JavaScript
function rotatedSearch(arr, target) {
let low = 0;
let high = arr.length - 1;
while (low <= high) {
const mid = Math.floor((low + high) / 2);
if (arr[mid] === target) return mid;
if (arr[low] <= arr[mid]) {
if (arr[low] <= target && target < arr[mid]) high = mid - 1;
else low = mid + 1;
} else {
if (arr[mid] < target && target <= arr[high]) low = mid + 1;
else high = mid - 1;
}
}
return -1;
}図解
計算量
毎回区間が半分になるので O(log n)、空間は O(1) です。回転 がない普通の ソート 済み配列でも同じコードが動きます (左半分 は常に ソート 済みとして扱われます)。
比較
| 配列 | 線形探索 | 普通の二分探索 | 回転対応版 |
|---|---|---|---|
ソート 済み | O(n) | O(log n) | O(log n) |
回転ソート | O(n) | 動かない | O(log n) |
| 未ソート | O(n) | 動かない | 動かない |
回転があるかないかを事前に判定する必要はありません。今回のアルゴリズムはどちらの場合も正しく動きます。
注意するポイント
arr[low] <= arr[mid]の 等号 を忘れない (要素 2 個やmid == lowのケースで重要)targetの範囲チェックは 左閉右開 (arr[low] <= target < arr[mid]) のような片側の境界に注意重複ありの回転ソート配列だとO(log n)を保証できなくなる (本問題では重複なし前提)
よくある間違い
arr[mid] == targetの判定を入れ忘れる- 等号 (
<=) と狭義不等号 (<) を間違える target == arr[low]やtarget == arr[high]の境界判定を入れ忘れる- 配列の長さ
0や1のケースでindex out of range
やってみよう
[4, 5, 6, 7, 0, 1, 2] から 0 を探すと index=4、3 を探すと -1。[5, 1, 3] から 3 を探すと index=2。[1] から 0 を探すと -1。
本問題のテストでは
重複なし配列のみを使うので、上記のシンプルな実装で十分です。
業務的には 回転ソート配列 という構造は珍しいですが、循環バッファ カレンダーのループ表示 音楽の再生位置 など、本質的に 回転 が関わるデータ構造はそこかしこにあります。考え方を覚えておくと応用がきくテクニックです。
よくある質問
Q. このトピックは実務でどう役立ちますか？
A. DB のクエリ最適化、API 設計、データ構造の選択など、設計判断の根拠になります。表面的にライブラリを使うだけでなく「なぜそれが速いのか」を理解できると、性能問題を未然に防げます。コーディング面接でも頻出のテーマです。
Q. 計算量はどう求めれば良いですか？
A. ループのネストごとに掛け算する、再帰なら漸化式から解く、というのが基本です。Big-O 表記は定数倍と低次の項を無視するため、n の指数（n²、n log n など）に注目してください。最悪・平均・最良の 3 つを意識すると説得力が増します。
Q. 覚えるべき定番アルゴリズムは何ですか？
A. 二分探索、クイックソート/マージソート、BFS/DFS、ダイクストラ、DP の基本問題（フィボナッチ・ナップサック）が必修です。これらを「白紙から書ける」状態にすると、応用問題が一気に解けるようになります。
次のレッスン
次は 第2章まとめクイズ で、昇順ソートされた配列がある位置で回転している配列に対し、target の index を O(log n) で探します を学びます。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- 回転ソート探索 の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. 回転ソート探索 とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
要件
- O(log n) で実装する
- 重複なし配列を前提とする
- 見つからない場合は -1 を返す
入出力例
test-cases.txt
rotatedSearch([4,5,6,7,0,1,2], 0) → 4
rotatedSearch([4,5,6,7,0,1,2], 5) → 1
rotatedSearch([4,5,6,7,0,1,2], 3) → -1
rotatedSearch([1,2,3,4,5], 3) → 2
rotatedSearch([1], 1) → 0
rotatedSearch([1], 0) → -1