# [leetcode 153. Find Minimum in Rotated Sorted Array](https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/)
<font color=#FFB800>Medium</font> 49.1%
- 限制
<ul>
<li><code>n == nums.length</code></li>
<li><code>1 <= n <= 5000</code></li>
<li><code>All the integers of nums are unique.</code></li>
<li><code>nums is sorted and rotated between 1 and n times. </code></li>
</ul>

- Solution - A
這題如果沒有限制時間複雜度的話其實是簡單的，只要循著找到最小值就好。所以先看一下用 $O(n)$ 所寫出的程式碼。
- 時間複雜度: $O(n)$
- 空間複雜度: $O(1)$
- 程式碼

    class Solution {
    public:
        int findMin(vector<int>& nums) {
            int result = *min_element(nums.begin(), nums.end());
            return result;
        }
    };

- Solution - B
- 想法 :
- 這裡的想法是如果考慮 nums[mid] 比第一個元素小，就代最小值還在 mid 之前，反之則在後面。
- 而這裡的動作就是要去找到從數列的開頭、且"不含最小值"的最長數列，而最小值就會藏在這一個數列後面。所以 start = mid + 1 會是去驗證所找的數列是不是有含到最小值。
- 時間複雜度: $O(log(n))$
- 空間複雜度: $O(1)$

- 程式碼

    class Solution {
    public:
        int findMin(vector<int>& nums) {
            int start = 0, end = nums.size() - 1, ans = nums[0];
            while (start <= end) {
                int mid = start + (end - start) / 2;
                if (nums[mid] >= nums[0])
                    start = mid + 1;
                else
                    ans = nums[mid], end = mid - 1; 
            }
            return ans;
        }
    };

- Sulotion - C (測資沒過，僅檢討哪裡錯)
- 想法 :
1. 簡單來說，就是一般沒改過的 binary search。
2. 在測資 {5, 1, 2, 3, 4} 、 {3, 1, 2} 、 {2, 1} 都有大問題。因為這種寫法會直接把中前段的最小值略過，造成找不到最小值。
3. 所以這個方法是不可行的，也就是這個方法只適合用在遞增的數列上。
- 程式碼

    class Solution {
    public:
        int findMin(vector<int>& nums) {
            int result = 0;
            int index_min = 0, index_max = nums.size() - 1, mid = 0;
            while(index_min < index_max)
            {
                mid = (index_min + index_max) /2;
                if(nums[index_min] > nums[index_max])
                {
                    index_min = mid;
                }
                else
                {
                    index_max = mid;
                }
            }
            result = nums[mid];
            return result;
        }
    };