# LeetCode Medium 33. Search in Rotated Sorted Array

tags: leetcode

問題

• Explore
• Problems

昇順で整列された配列が既に知らないある場所で回転していると仮定しなさい

(つまり, [0,1,2,4,5,6,7]は[4,5,6,7,0,1,2]になっているかも知れない)

探索する目標の値が与えられる. もし配列内に見つかったらそのインデックスを返せ. そうでなければ-1を返せ

配列内に同じ値はないと仮定しても良い

アルゴリズムにかかる時間計算量は$O(\log n)$でなければならない

アイデア

配列内に単調性があるので二分探索を使います. ただ, ここでは昇順な配列がある場所で回転しているのでそれを考慮したアルゴリズムにする必要が有ります

解法

探索する値をtargetとします

• まずは与えられた配列が空のときは-1を返します
• 配列の左端をleft, 右端をrightとします
• 左端が右端より左にある間(left < right)以下の手続きを繰り返します
• 左端と右端の間をmidとします
• このとき配列は次の2パターンが考えられます
  • [7,8,9,1,2,3,4,5,6]のように真ん中より左の間から昇順となる配列が始まるもの
  • [4,5,6,7,8,9,1,2,3]のように真ん中から右の間から昇順となる配列が始まるもの
• 前者の場合
  • targetが中央の値と右端の値の間であれば右側に探索する範囲をずらします
    • 片方の条件だけだと左側の要素も当てはまります
  • そうでなければ左側に
• 後者の場合
  • targetが中央の値と左端の値の間ときは左側に探索する範囲をずらします
    • 片方の条件だけだと右側の要素も当てはまります
  • そうでなければ左側に
• このようにして配列を全て探索しても見つからないときは左端の値をtargetと比較して同じならleft, 違うなら-1を返します
  • これは終了条件がleft >= rightであり, 右側が配列外を参照している可能性があるからです

計算量

• 時間計算量
  • $O(\log n)$
• 空間計算量
  • $O(1)$

C++

class Solution {
public:
  int search(vector<int>& nums, int target) {
    if (nums.empty()) return -1;
    
    int left = 0, right = nums.size() - 1;
    
    while (left < right) {
      int mid = left + (right - left) / 2;
      if (nums[mid] == target) return mid;
      
      if (nums[mid] < nums[right]) {
        if (nums[mid] < target && target <= nums[right])
          left = mid + 1;
        else
          right = mid - 1;
      } else {
        if (nums[left] <= target && target < nums[mid])
          right = mid - 1;
        else 
          left = mid + 1;
      }
    }
    if (target == nums[left])
      return left;
    else
      return -1;
  }
};