C++实现LeetCode(153.寻找旋转有序数组的最小值)

[LeetCode] 153. Find Minimum in Rotated Sorted Array 寻找旋转有序数组的最小值

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

Find the minimum element.

You may assume no duplicate exists in the array.

Example 1:

Input: [3,4,5,1,2]
Output: 1

Example 2:

Input: [4,5,6,7,0,1,2]
Output: 0

这道寻找旋转有序数组的最小值肯定不能通过直接遍历整个数组来寻找，这个方法过于简单粗暴，这样的话，旋不旋转就没有意义。应该考虑将时间复杂度从简单粗暴的 O(n) 缩小到 O(lgn)，这时候二分查找法就浮现在脑海。这里是比较难的那一类，没有固定的 target 值比较，而是要跟数组中某个特定位置上的数字比较，决定接下来去哪一边继续搜索。这里用中间的值 nums[mid] 和右边界值 nums[right] 进行比较，若数组没有旋转或者旋转点在左半段的时候，中间值是一定小于右边界值的，所以要去左半边继续搜索，反之则去右半段查找，最终返回 nums[right] 即可，参见代码如下：

解法一：

									class Solution {

									public:

									    int findMin(vector<int>& nums) {

									        int left = 0, right = (int)nums.size() - 1;

									        while (left < right) {

									            int mid = left + (right - left) / 2;

									            if (nums[mid] > nums[right]) left = mid + 1;

									            else right = mid;

									        }

									        return nums[right];

									    }

									};