[leetcode_153]Find Minimum in Rotated Sorted Array

这个题挺有意思的，给定一个排序的数组：1,2,3,4,5,6,7，但是这个数组经过了一个旋转，比如，4,5,6,7,1,2,3。这个时候求这个数组中最小的元素。O(n)一定能解出来。记得去年面试滴滴打车的时候问过类似的问题。当时笃定是二分查找，但是感觉说得不清楚。这次做题显然思路就清晰了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


class Solution {
public:
    void binarySearch(vector<int>& nums, int left, int right, int &min)
    {
        if (left > right)
        {
            return ;
        }
        int mid = (left + right) / 2;
        if (nums[mid] >= min)
        {
            binarySearch(nums, left, mid - 1, min);
            binarySearch(nums, mid+1, right, min);
        }
        else
        {
            min = nums[mid];
            binarySearch(nums, left, mid - 1, min);
        }
    }

    int findMin(vector<int>& nums) {
        int min = nums[0];
        binarySearch(nums, 0, nums.size() - 1, min);
        return min;
    }
};