已知一個長度為 n 的數組，預先按照升序排列，經由 1 到 n 次 旋轉 后，得到輸入數組。例如，原數組 nums = [0,1,2,4,5,6,7] 在變化后可能得到：
若旋轉 4 次，則可以得到 [4,5,6,7,0,1,2]
若旋轉 4 次，則可以得到 [0,1,2,4,5,6,7]
注意，數組 [a[0], a[1], a[2], …, a[n-1]] 旋轉一次 的結果為數組 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。

給你一個元素值 互不相同 的數組 nums ，它原來是一個升序排列的數組，并按上述情形進行了多次旋轉。請你找出并返回數組中的 最小元素 。

示例 1：

輸入：nums = [3,4,5,1,2]
輸出：1
解釋：原數組為 [1,2,3,4,5] ，旋轉 3 次得到輸入數組。

解題思路

分成3鐘情況討論
7 8 9 1 2 3 4 5 6
nums[l]<nums[mid]
情況一：nums[l]=1 nums[mid]=3 nums[r]=5 在左邊區間招找
情況二：nums[l]=7 nums[mid]=9 nums[r]=2 在右邊區間找

7 8 9 1 2 3 4 5 6
nums[l]=7 nums[mid]=3
nums[l]>nums[mid] 所以可以確定最小值只會在左邊區間產生

2 3 4 5 6 1
nums[l]=nums[mid]=6 nums[r]=1
nums[l]==nums[mid] 結果只會在nums[l]和nums[r]中產生，選出最小值即可

代碼

class Solution {public int findMin(int[] nums) {int l=0,r=nums.length-1;while (l<=r){int mid=(r-l)/2+l;if(nums[l]==nums[mid]) {return Math.min(nums[r],nums[l]);}else if(nums[l]<nums[mid]){if(nums[r]<nums[l])l=mid;else  r=mid;}else {r=mid;}}return nums[r];}
}