Find Minimum in Rotated Sorted A

Find Minimum in Rotated Sorted Array.png

===================== 解題思路 =====================

一樣用二分法 先求出 mid = left + (right - left) / 2
考慮兩種情形:

1. mid 的儲存值比 vector 尾端的數還大 代表 mid 以及 mid 之前的數都是 rotate 過的跑到前面 不可能是原本的頭(最小值) 所以只檢查 mid 之後的數 ( mid ~ right )
2. mid 的儲存值比 vector 尾端的數小 相反的只檢查 mid 前面的數 (left ~ mid)

接著就是等 while ( left + 1 < right ) 結束後 檢查 left 跟 right 的數值 誰小就是答案

===================== C++ code ====================

<pre><code>
class Solution {

public:

/**
 * @param num: a rotated sorted array
 * @return: the minimum number in the array
 */
int findMin(vector<int> &num) {
    if(num.size() == 0) return -1;
    int left = 0, right = num.size() -1, end = num.size() -1;
    while(left + 1 < right)
    {
        int mid = left + (right - left) / 2;
        if(num[mid] > num[end]) left = mid;
        else right = mid;
    }
    return num[right] > num[left]? num[left] : num[right];
}

};
<code><pre>