Find Minimum in Rotated Sorted Array

1 解析

这道题是本题的另外一种求解目标，都是同一种题型变换而来。核心还是二分查找

2 分析

有序序列绕着某个未知坐标旋转，而且是没有重复的数字，所以不管怎样旋转，最终序列由两段有序序列组成，这是关键，题目求解序列的最小值，那么无非就是在这两段有序序列的最小值之间选择一个值较小的。我们可以采用二分查找的思想，每次从中间元素mid开始，如果中间元素mid小于或等于最右边缘元素right，那么[mid, right]之间的元素一定是有序的序列，则最小元素即为序列的开头元素mid，然后继续[left, mid -1]之间去查找，所获得[left, mid -1]之间的最小值与[mid, right]之间最小值相比较，取值最小的作为当前最小值，然后继续更新left和right的值，缩小搜索的范围，直到left大于right为止。

3 实现

例如：4     5      6      7      0      1       2        res = 1000000[初始化]

第一趟： 4     5      6      7      0      1       2       left = 0       right = 6    mid = (left+right) / 2 = 3    res = 4

第二趟： 4     5      6      7      0      1       2       left = 4       right = 6    mid = (left+right) / 2 = 5    res = 1

第三趟： 4     5      6      7      0      1       2       left = 4       right = 4    mid = (left+right) / 2 = 4    res = 0

第四趟： left = 4    >   right = 3    跳出结束

class Solution { public: int findMin(vector<int>& nums) { int left = 0; int right = nums.size() - 1; int res = 1000000; while (left <= right){ int mid = (left + right) / 2; if (nums[mid] <= nums[right]){ //右边局部有序[mid, right] res = min(res, nums[mid]); right = mid - 1; } else { if (nums[left] <= nums[mid]){ //左边局部有序[left, mid] res = min(nums[left], res); left = mid + 1; //在右边查找 } else{ left++; //往右继续缩小范围 } } } return res; } };