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.

給定一個陣列 nums 他會旋轉了 1 到 n 次，比如 [0,1,2,3,4,5,6,7] 可能變為 [4,5,6,7,0,1,2] 如果它被旋轉了 4 次，[0,1,2,4,5,6,7] 如果它被旋轉了 7 次，雖然題目提到陣列會旋轉但其實這只是陷阱，用 Binary Search 即可找到最小值。

Coding

/**
 * @param {number[]} nums
 * @return {number}
*/
var findMin = function(nums) {
    let l = 0, r = nums.length - 1;
    let min = Infinity;
    while (l <= r) {
      const mid = Math.floor((r - l) / 2) + l;
      min = Math.min(nums[mid], min);

      // min in right side
      if (nums[mid] > nums[r]) {
        l = mid + 1;
      } else {
        // min in left side
        r = mid - 1;
      }
    }
    return min;
};

裡用 l 和 r 指標指定陣列的兩端並找到中間的值 mid，如果 mid 的值大於 r 的值，代表最小值在 mid 的右邊，將 l 移動到 mid 右邊一格再次找 l 跟 r 的 mid，持續找到最小值。

Time complexity: O(logn)