# 153. Find Minimum in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e.,  `[0,1,2,4,5,6,7]` might become  `[4,5,6,7,0,1,2]`).

Find the minimum element.

You may assume no duplicate exists in the array.

**Example 1:**

```
Input: [3,4,5,1,2] 
Output: 1
```

**Example 2:**

```
Input: [4,5,6,7,0,1,2]
Output: 0
```

**Solution**

是這題33.-search-in-rotated-sorted-array的基礎題目

```java
class Solution {
    public int findMin(int[] nums) {
        int lo = 0;
        int hi = nums.length - 1;
        while(hi > lo){
            int mid = lo + (hi-lo)/2;
            if(nums[hi] > nums[mid]){
                hi = mid;
            }
            else{
                lo = mid+1;
            }
        }
        return nums[lo];
    }
}
```

這題有一個重點, 就是為什麼只能用nums\[mid] < nums\[hi]來當判斷的conidtion?&#x20;

其實nums\[mid] < nums\[lo], 應該也可以推論出pivot point應該在left hand side, 為何執行期會有錯?

```java
class Solution {
    public int findMin(int[] nums) {
        int lo = 0;
        int hi = nums.length - 1;
        while(hi > lo){
            int mid = lo + (hi-lo)/2;
            if(nums[mid] < nums[lo]){
                hi = mid;
            }else{
                lo = mid+1;
            }
        }
        return nums[lo];
    }
}
```

Input: \[3,4,5,1,2] Output: 2 Expected: 1

原因在於, 在searching的過程monotonicity被破壞了, 出現了有序的interval \[1,2], 此時如果用原來的邏輯,會一直以為pivot在right side, 所以不同的lo = mid+1, 導致錯誤的結果。

其實理論上因為它的monotonicity在過程中都會被破壞, 都要進行檢查才是, 即使是透過nums\[mid] < nums\[hi]當作condition也是依樣, 應改成

```java
    public int findMin(int[] nums) {
        int lo = 0;
        int hi = nums.length - 1;
        while(hi > lo){
            int mid = lo + (hi-lo)/2;
            if(nums[lo] <= nums[hi]){ //表示有序, monotonicity已經消失
                return nums[lo];
            }
            if(nums[mid] < nums[lo]){// nums[mid] < nums[hi]也可以
                hi = mid;
            }else{
                lo = mid+1;
            }
        }
        return nums[lo];
    }
}
```
