###### tags: `Leetcode` `medium` `binary search` `python` `c++` `Top 100 Liked Questions`

# 153. Find Minimum in Rotated Sorted Array

## [題目連結:] https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/description/

## 題目:
Suppose an array of length ```n``` sorted in ascending order is **rotated** between 1 and n times. For example, the array ```nums = [0,1,2,4,5,6,7]``` might become:

* ```[4,5,6,7,0,1,2]``` if it was rotated 4 times.
* ```[0,1,2,4,5,6,7]``` if it was rotated 7 times.

Notice that **rotating** an array ```[a[0], a[1], a[2], ..., a[n-1]]``` **1** time results in the array ```[a[n-1], a[0], a[1], a[2], ..., a[n-2]]```.

Given the sorted rotated array nums of **unique** elements, return the minimum element of this array.

You must write an algorithm that runs in ```O(log n) time```.

## 解題想法:
* 題目為給一**旋轉過**的數組:
* 求數組中最小值，且time: O(logN)
* 相關類型題目可參考
* [33. Search in Rotated Sorted Array](/Be1uCkocTO-iWb2f-Ne3-Q)
* [81. Search in Rotated Sorted Array II](/GF7mD5tES_WtMiU9TSGw2w)

* 要求 O(logN): **往binary search思考**
* 數組分為: left…mid…right
* 先判斷左(left-mid)右(mid-right)邊哪段是正常的
* 以右半段為例，正常為由小到大
* ex: nums=[3,4,5,1,2]
* nums[mid]=5, nums[right]=2
* 不正常排序，表示最小值在此段
* 所以left=mid+1 縮小判斷範圍
* 若右半段小到大正常排序，表示最小值在前半段
* right=mid-1 縮小判斷範圍

## Python:

#binary search
class Solution(object):
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res=float('inf')
        left=0
        right=len(nums)-1
        while left<=right:
            mid=(left+right)//2
            res=min(res,nums[mid])
            #表示小的在後半段
            if nums[mid]>nums[right]:
                left=mid+1
            else:
                right=mid-1
        return res
                
result = Solution()
nums = [4,5,6,7,0,1,2]
ans = result.findMin(nums)
print(ans)

## C++:

#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
    int findMin(vector<int>& nums) {
        int res=5000, left=0, right=nums.size()-1;
        while (left<=right){
            int mid=(left+right)/2;
            res=min(res,nums[mid]);
            if (nums[mid]>nums[right])
                left=mid+1;
            else
                right=mid-1;
        }
        return res;
    }
};

int main(){
    Solution res;
    vector<int> nums ={3,4,5,1,2};
    int ans=res.findMin(nums);
    cout<<ans<<endl;
    return 0;
}