Search in Rotated Sorted Array（回転ソート配列の検索）
Search in Rotated Sorted Array（回転ソート配列の検索）とは
途中で回転された昇順配列からtargetの位置を探す課題です。
配列全体が単純な昇順でなくても、局所的な順序を使って二分探索できます。
判断するときに確認すること
- どちら側が整列済みか判定できるか
- targetが境界値の場合を含めているか
- 探索範囲が必ず狭くなるか
具体例で整理する
避けたい判断
回転位置を無視して通常の二分探索を行う。
条件が分かる判断
整列済みの範囲にtargetが含まれるか確認して、残す側を決める。
設計とレビューで使う
このページの推奨は次のとおりです。
中央を見て左右どちらが整列済みか判定し、targetを含む側へ探索範囲を絞る。