153. Find Minimum in Rotated Sorted Array

https://leetcode.com/problems/search-in-rotated-sorted-array/description/

Suppose a sorted array 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).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Thoughts

从小到大排好序的数组从某个元素开始整体移到前面，让找移动后数组最小的值。分为两种情况，从分割点前后各有一个递增序列，后面的都比nums[0]小，且最小点就是分割点；或分割点为0元素，也就是数组实际没有变，最小点即nums[0]。无论哪种情况，当落在比nums[0]大于等于的点意味着在前半边，否则在后半边，以此二分后，再把找出来的和nums[0]比较。

/*
 * @lc app=leetcode id=153 lang=cpp
 *
 * [153] Find Minimum in Rotated Sorted Array
 */

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