LEETCODE 153. Find Minimum in Rotated Sorted Array

题目内容

题目给出一个数组，这个数组是将一个已经按升序排序好的数组，经过若干次循环移位得到的，我们要从中找到最小的值。

解题思路

对于这种在已经排序好的数组中找某个值，我们很容易想到的是二分搜索法。这道题也可以采用二分搜索来解决。二分搜索的过程中，我们会逐渐将搜索范围减半，如果我们可以保证每次减半之后，目标值都存在这个减半后的范围内，那么，当这个范围内剩下1个元素的时候，这个元素就是我们要的目标值。 假定搜索范围是[start, end]，其中初始状态时， start=0,end=nums.size()−1 ，中间值 mid=start+end2 。这时候会有2中情况：

nums[mid] > nums[end]，这种情况说明当前搜索范围的后半部分依然不是有序的，目标值应该在后半部分，更新start=mid+1，同时更新mid的值。nums[mid] <= nums[end]，这种情况说明后半部分是按照升序排序好的了，那么nums[mid]前面可能存在比nums[mid]更小的值，所以应该从前半部分继续搜索，更新end=mid，同时更新mid的值。 当start=end的时候，搜索范围内只剩下一个元素，那么这个元素就是最小值。

实现代码

class Solution { public: int findMin(vector<int>& nums) { int start = 0, end = nums.size() - 1; while (start < end) { int mid = (start + end) / 2; if (nums[mid] > nums[end]) { start = mid + 1; } else { end = mid; } } return nums[start]; } };