# LeetCode 33. Search in Rotated Sorted Array
[LeetCode 33. Search in Rotated Sorted Array](https://hackmd.io/pKlP9hwPSR6tdgkSR7mQMw?both) (<font color="#FFB800"> Medium</font> 通過率: 40.5%)

## 限制條件
<ul>
<li>1 &lt;= nums.length &lt;= 5000</li>
<li>-10⁴ &lt;= nums[i] &lt;= 10⁴</li>
<li>All values of nums are unique.</li>
<li>nums is an ascending array that is possibly rotated.</li>
<li>-10⁴ &lt;= target &lt;= 10⁴</li>
</ul>

### 解法 1
這題因為陣列長度不長，所以其實不用使用到 binary search，用線性去解其實就可以解決，但因為這題偏向 binary search，所以嘗試使用 binary search 去解。
但是我自己的寫法是為了不要移動任何在記憶體上的位子，所以會切分出左右邊的陣列，再依序用 binary search 尋找。這樣的寫法在切分上要很清楚，我就是因為切得不好，所以在 debug 時候很久。(有 STL 用 STL…)，而且還比較慢(7ms)。

- 時間複雜度: O(lg(n))
- 空間複雜度: O(1)

class Solution {
public:
    int search(vector<int>&amp; nums, int target) {
        // 找出旋轉的位置
        int min_index =0, max_index = nums.size()-1;
        int cur_index = (max_index - min_index)/2 + min_index;
        int max_num = nums[0];
        while(min_index &lt;= max_index)
        {
            cur_index = (max_index - min_index)/2 + min_index;
            cout &lt;&lt; "A : " &lt;&lt; min_index &lt;&lt; ' ' &lt;&lt; cur_index &lt;&lt; ' ' &lt;&lt; max_index &lt;&lt;'\n';
            if(nums[cur_index] == max_num)
                max_num = cur_index - 1;
            if(nums[cur_index] &lt; max_num)
                max_index = cur_index - 1;
            else
                min_index = cur_index + 1;
        }
        if(nums.size() &gt; max_index + 1 &amp;&amp; nums[max_index] &gt; nums[max_index + 1])
            max_index++;
        int split_index = max_index;
        min_index = 0, max_index = split_index;
        while(min_index &lt;= max_index)
        {
           // 這裡要寫的是 (max - min) / 2 + min 才對，不可以直接相減
            cur_index = (max_index - min_index) / 2 + min_index;
            cout &lt;&lt; "B : " &lt;&lt; min_index &lt;&lt; ' ' &lt;&lt; cur_index &lt;&lt; ' ' &lt;&lt; max_index &lt;&lt;'\n';
            if(nums[cur_index] == target) return cur_index;
            else if(nums[cur_index] &lt; target) min_index = cur_index + 1;
            else if(nums[cur_index] &gt; target) max_index = cur_index - 1;
            cout &lt;&lt; "B : " &lt;&lt; min_index &lt;&lt; ' ' &lt;&lt; cur_index &lt;&lt; ' ' &lt;&lt; max_index &lt;&lt;'\n';
        }
        min_index = split_index, max_index = nums.size() - 1;
        while(min_index &lt;= max_index)
        {
            // 這裡要寫的是 (max - min) / 2 + min 才對，不可以直接相減
            cur_index = (max_index - min_index) / 2 + min_index;
            cout &lt;&lt; "C : " &lt;&lt; min_index &lt;&lt; ' ' &lt;&lt; cur_index &lt;&lt; ' ' &lt;&lt; max_index &lt;&lt;'\n';
            if(nums[cur_index] == target) return cur_index;
            else if(nums[cur_index] &lt; target) min_index = cur_index + 1;
            else if(nums[cur_index] &gt; target) max_index = cur_index - 1;
            cout &lt;&lt; "C : " &lt;&lt; min_index &lt;&lt; ' ' &lt;&lt; cur_index &lt;&lt; ' ' &lt;&lt; max_index &lt;&lt;'\n';
        }
        return -1;
    }
};

### 解法 2
這是使用 STL 的解法，比較快 (4ms)

- 時間複雜度: O(lg(n))
- 空間複雜度: O(1)

class Solution
{
public:
    int search(vector<int>&amp; nums, int target)
    {
        vector<int>::iterator current= find(nums.begin(), nums.end(), target);
        if (current == nums.end())
        {
            return -1;
        }
        return current - nums.begin();
    }
};