hot100-52寻找旋转排序数组中的最小值

一、题目

给定一个长度为n的数组，原本按照升序排列，经过n次旋转后得到的数组，找出并返回数组中的最小元素。

二、思路

1、二分查找，数组虽然被旋转了，但是也保留了部分有序性，数组分为两端升序数组，最小值出现在第二段开头，最小值右边的所有元素小于等于最左边的元素。

比较nums[mid] 和nums[right]，因为和right比能明确区分左右段；而left在旋转后可能很大（如[4,5,6,7,0,1,2]中left=4），无法判断。

三、代码

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

注：为什么是left < right？

因为这道题目不可以排除mid（只有左右两部分），所以right = mid，这种情况下 left=right，容易死循环，left = right = mid，永远在while里，所以终止条件应该是 left = right。所以while中为 left<right。