###### tags: `Array`
<h1>
Leetcode 153. Find Minimum in Rotated Sorted Array
</h1>
<ol>
<li>問題描述</li>
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:<br><br>
<ul>
<li>[4,5,6,7,0,1,2] if it was rotated 4 times.</li>
<li>[0,1,2,4,5,6,7] if it was rotated 7 times.</li>
</ul><br>

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.<br><br>

Example 1:

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2:

Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7]
and it was rotated 4 times.

Example 3:

Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17]
and it was rotated 4 times.

<li>Input的限制</li>
<ul>
<li>1 <= nums.length(n) <= 5000</li>
<li>-5000 <= nums[i] <= 5000</li>
<li>All the integers of nums are unique.</li>
<li>nums is sorted and rotated between 1 and n times.</li>
</ul>
<br>

<li>思考流程</li>
<ul>
<li>Binary Search</li>
要從 rotated sorted array 裡面找出最小的元素，關鍵在於找出 inflection point，一般的 sorted array 正常都是由小到大排列，由於 array 經過了 rotated，所以除了正常的由小到大排序，還會有一小段是由大變小，那就是 inflection point 的所在。
<br>
<br>
在整個變形的 binary search 中，我們會先檢查 mid point 的前中後是否存在 inflection point。若不存在，則我們拿 arr[mid] 與 arr[0] 進行比較，若 arr[mid] < arr[0]，代表 inflection point 位於 arr[mid] 的左半部；若 arr[mid] > arr[0]，代表 inflection point 位於 arr[mid] 的右半部。重複這個過程直到找到 inflection point 為止。
<br>
<br>
在可能的 input 中，如果 input size == 2，則可能會出問題。因為計算 mid = ( right + left ) // 2，所以 mid 會等於 arr[0]，這時候要先執行 arr[mid] > arr[mid+1] 這個條件，才不會發生 IndexError。如果 arr[mid] 本身是最小值，我們必須在一開始檢查 array 是否是正常的 sorted array，來排除掉這樣的情況。
<br>
<br>
Binary search 利用對半切的方式，每次會捨棄一半的 input，故 time complexity 是 O(logN)。紀錄上使用了 right, mid, and left，故 space complexity 是 O(1)。
<br>
<br>
Time Complexity: O(logN); Space Complexity: O(1)
<br>
<br>
</ul>
<li>測試</li>
<ul>
<li>test 1( edge case )</li>
如果 input 為 empty list，則須回報錯誤訊息。
<li>test 2( edge case )</li>
Input: nums = [5, 2]<br>
Output: 2
<li>test 3( edge case )</li>
Input: nums = [2, 5]<br>
Output: 2
<li>test 4</li>
Input: nums = [5, 1, 2, 3, 4]<br>
Output: 1
<li>test 5</li>
Input: nums = [3, 4, 5, 1, 2]<br>
Output: 1
</ol>