Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e.,0 1 2 4 5 6 7might become4 5 6 7 0 1 2).
Find the minimum element.
You may assume no duplicate exists in the array.
题目标签：Array, Binary Search
题目给了我们一个 旋转有序 数组，让我们找到最小值。如果是在还没有旋转的情况下，那么我们知道，最小值就是第一个数字。
那么当遇到旋转的情况呢，我们就需要找到那个 “断点” 的两个数字，换句话说，就是最大值和最小值，而且这两个数字一定是相邻的。
我们来看一下例子：
0 1 2 4 5 6 7直接返回第一个数字
1 2 4 5 6 7 0返回7 和0 中小的那个数字
2 4 5 6 7 0 1
4 5 6 7 0 1 2
5 6 7 0 1 2 4
6 7 0 1 2 4 5
7 0 1 2 4 5 6
利用二分法来找到 最大和最小的 两个数字。
rule 1： 如果 mid 小于 left， 意味着最大的数字在左边，继续去左边找，把right = mid， 这里要包括mid，因为mid 可能是最小的数字；
rule 2： 如果 mid 大于 right， 意味着最小的数字在右边，继续去右边找，把left = mid， 这里要包括mid， 因为mid 可能是最大的数字。
当left 和right 相邻的时候，返回小的数字就可以了。
Java Solution:
Runtime beats 53.07%
完成日期：08/30/
关键词：Array， Binary search
关键点：旋转中，min 和 max 必然是相邻的，利用二分法找到min 和max
1 class Solution 2 { 3public int findMin(int[] nums) 4{ 5 if(nums.length == 1) 6 return nums[0]; 78 int left = 0; 9 int right = nums.length - 1;10 11 if(nums[left] < nums[right])12 return nums[0];13 14 while(left + 1 != right)15 {16 int mid = left + (right - left) / 2;17 18 if(nums[mid] < nums[left]) // if left is greater than mid, move to left19 right = mid;20 else if(nums[mid] > nums[right]) // if mid one is greater than right, move to right21 left = mid;22 }23 24 // if there are only two number25 return Math.min(nums[left], nums[right]);26}27 }
参考资料：N/A
LeetCode 算法题目列表 -LeetCode Algorithms Questions List
如果觉得《LeetCode 153. Find Minimum in Rotated Sorted Array （在旋转有序数组中找到最小值）》对你有帮助，请点赞、收藏，并留下你的观点哦！
